
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>6.树论 · 计算机 ,java , 大数据 基础知识体系</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="hzh">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-toggle-chapters/toggle.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-code/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="7.树论例题.html" />
    
    
    <link rel="prev" href="5.排序列题.html" />
    

    
    
    
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        <li class="header">操作系统</li>
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../操作系统/1.基本概述.html">
            
                <a href="../操作系统/1.基本概述.html">
            
                    
                    1.操作系统基本概述
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../操作系统/2.进程管理之进程与线程.html">
            
                <a href="../操作系统/2.进程管理之进程与线程.html">
            
                    
                    2.进程管理之进程与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../操作系统/3.进程管理之处理机调度.html">
            
                <a href="../操作系统/3.进程管理之处理机调度.html">
            
                    
                    3.进程管理之处理机调度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../操作系统/4.进程管理之进程同步.html">
            
                <a href="../操作系统/4.进程管理之进程同步.html">
            
                    
                    4.进程管理之进程同步
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../操作系统/5.内存管理之基本概念.html">
            
                <a href="../操作系统/5.内存管理之基本概念.html">
            
                    
                    5.内存管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../操作系统/6.内存管理之虚拟内存.html">
            
                <a href="../操作系统/6.内存管理之虚拟内存.html">
            
                    
                    6.内存管理之虚拟内存
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../操作系统/7.IO设备管理之基本概念.html">
            
                <a href="../操作系统/7.IO设备管理之基本概念.html">
            
                    
                    7.IO设备管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../操作系统/8.面试题总结一.html">
            
                <a href="../操作系统/8.面试题总结一.html">
            
                    
                    8.面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">计算机网络篇</li>
        
        
    
        <li class="chapter " data-level="2.1" data-path="../计算机网络/1.计算机网络入门基础概念.html">
            
                <a href="../计算机网络/1.计算机网络入门基础概念.html">
            
                    
                    1.计算机网络入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="../计算机网络/2.计算机网络通信基础.html">
            
                <a href="../计算机网络/2.计算机网络通信基础.html">
            
                    
                    2.计算机网络通信入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="../计算机网络/3.数据链路层.html">
            
                <a href="../计算机网络/3.数据链路层.html">
            
                    
                    3.数据链路层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="../计算机网络/4.网络层1.html">
            
                <a href="../计算机网络/4.网络层1.html">
            
                    
                    4.网络层(一)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.5" data-path="../计算机网络/5.网络层2.html">
            
                <a href="../计算机网络/5.网络层2.html">
            
                    
                    5.网络层(二)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.6" data-path="../计算机网络/6.传输层.html">
            
                <a href="../计算机网络/6.传输层.html">
            
                    
                    6.传输层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.7" data-path="../计算机网络/7.应用层.html">
            
                <a href="../计算机网络/7.应用层.html">
            
                    
                    7.应用层(⭐)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.8" data-path="../计算机网络/10.HTTP相关协议.html">
            
                <a href="../计算机网络/10.HTTP相关协议.html">
            
                    
                    8.HTTP相关及发展
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.9" >
            
                <span>
            
                    
                    9.websocket
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="2.10" data-path="../计算机网络/9.面试题二.html">
            
                <a href="../计算机网络/9.面试题二.html">
            
                    
                    面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">数据结构篇</li>
        
        
    
        <li class="chapter " data-level="3.1" data-path="1.图论.html">
            
                <a href="1.图论.html">
            
                    
                    1.图论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.2" data-path="2.图论例题.html">
            
                <a href="2.图论例题.html">
            
                    
                    2.图论例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="3.散列表.html">
            
                <a href="3.散列表.html">
            
                    
                    3.散列表
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.4" data-path="4.排序算法.html">
            
                <a href="4.排序算法.html">
            
                    
                    4.排序算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.5" data-path="5.排序列题.html">
            
                <a href="5.排序列题.html">
            
                    
                    5.排序算法例题
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="3.6" data-path="6.树论.html">
            
                <a href="6.树论.html">
            
                    
                    6.树论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.7" data-path="7.树论例题.html">
            
                <a href="7.树论例题.html">
            
                    
                    7.树论例题.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.8" data-path="9.模板.html">
            
                <a href="9.模板.html">
            
                    
                    数据结构模板
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">算法篇</li>
        
        
    
        <li class="chapter " data-level="4.1" data-path="../算法/leetCode周赛题解.html">
            
                <a href="../算法/leetCode周赛题解.html">
            
                    
                    leetCode周赛记录
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="../算法/1.时间复杂度.html">
            
                <a href="../算法/1.时间复杂度.html">
            
                    
                    1.时间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.3" data-path="../算法/2.深度优先搜索.html">
            
                <a href="../算法/2.深度优先搜索.html">
            
                    
                    2.深度优先搜索算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.4" data-path="../算法/2.深度优先搜索题目集.html">
            
                <a href="../算法/2.深度优先搜索题目集.html">
            
                    
                    2.深搜题目集
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.5" data-path="../算法/3.广度优先搜索.html">
            
                <a href="../算法/3.广度优先搜索.html">
            
                    
                    3.广度优先搜索算法
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">JVM篇</li>
        
        
    
        <li class="chapter " data-level="5.1" data-path="../jvm/1.jvm内存结构.html">
            
                <a href="../jvm/1.jvm内存结构.html">
            
                    
                    1.jvm内存结构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                <a href="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                    
                    2.HotSpot虚拟机对象探秘.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.3" data-path="../jvm/3.对象存亡与垃圾收集算法.html">
            
                <a href="../jvm/3.对象存亡与垃圾收集算法.html">
            
                    
                    3.对象存亡与垃圾收集算法.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.4" data-path="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                <a href="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                    
                    4.HotSpot的算法细节与垃圾收集器.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.5" data-path="../jvm/5.内存分配与回收策略.html">
            
                <a href="../jvm/5.内存分配与回收策略.html">
            
                    
                    5.内存分配与回收策略.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.6" data-path="../jvm/6.类文件结构.html">
            
                <a href="../jvm/6.类文件结构.html">
            
                    
                    6.类文件结构.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.7" data-path="../jvm/7.类加载机制.html">
            
                <a href="../jvm/7.类加载机制.html">
            
                    
                    7.类加载机制.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.8" data-path="../jvm/8.jvm逃逸分析.html">
            
                <a href="../jvm/8.jvm逃逸分析.html">
            
                    
                    8.逃逸分析技术
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">多线程篇</li>
        
        
    
        <li class="chapter " data-level="6.1" data-path="../多线程/basic/0.多线程路线图.html">
            
                <a href="../多线程/basic/0.多线程路线图.html">
            
                    
                    1.多线程学习路线图
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="../多线程/basic/0.java内存模型与线程.html">
            
                <a href="../多线程/basic/0.java内存模型与线程.html">
            
                    
                    2.java内存模型与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="../多线程/3.并行程序基础.html">
            
                <a href="../多线程/3.并行程序基础.html">
            
                    
                    2.并行程序基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                <a href="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                    
                    3.happenBefore与jvm指令重排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="../多线程/basic/1.synchronized与volatile.html">
            
                <a href="../多线程/basic/1.synchronized与volatile.html">
            
                    
                    4.synchronized与volatile.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="../多线程/basic/2.ThreadLocal.html">
            
                <a href="../多线程/basic/2.ThreadLocal.html">
            
                    
                    5.ThreadLocal.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="../多线程/cas/1.乐观锁与悲观锁.html">
            
                <a href="../多线程/cas/1.乐观锁与悲观锁.html">
            
                    
                    6.乐观锁与悲观锁.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="../多线程/cas/2.CAS与atomic类.html">
            
                <a href="../多线程/cas/2.CAS与atomic类.html">
            
                    
                    7.CAS与atomic类.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.9" data-path="../多线程/aqs/1.AQS.html">
            
                <a href="../多线程/aqs/1.AQS.html">
            
                    
                    8.AQS.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.10" data-path="../多线程/aqs/2.基于AQS的并发工具.html">
            
                <a href="../多线程/aqs/2.基于AQS的并发工具.html">
            
                    
                    9.基于AQS的并发工具.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.11" data-path="../多线程/blockingQueue/1.阻塞队列.html">
            
                <a href="../多线程/blockingQueue/1.阻塞队列.html">
            
                    
                    10.阻塞队列.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.12" data-path="../多线程/pond/1.线程池与底层原理.html">
            
                <a href="../多线程/pond/1.线程池与底层原理.html">
            
                    
                    11.线程池与底层原理.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.13" data-path="../多线程/10面试题一.html">
            
                <a href="../多线程/10面试题一.html">
            
                    
                    12.面试题一
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.14" data-path="../多线程/10面试题二.html">
            
                <a href="../多线程/10面试题二.html">
            
                    
                    13.面试题二.md
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">java集合篇</li>
        
        
    
        <li class="chapter " data-level="7.1" data-path="../basic/collection/1.java集合.html">
            
                <a href="../basic/collection/1.java集合.html">
            
                    
                    1.集合架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="../basic/collection/2.HashMap源码分析.html">
            
                <a href="../basic/collection/2.HashMap源码分析.html">
            
                    
                    2.hashMap底层原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.3" data-path="../basic/collection/3.ConcurrentHashMap分析.html">
            
                <a href="../basic/collection/3.ConcurrentHashMap分析.html">
            
                    
                    3.ConcurrentHashMap分析
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">设计模式篇</li>
        
        
    
        <li class="chapter " data-level="8.1" >
            
                <span>
            
                    
                    1.创造型模式
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="8.2" data-path="../设计模式/factory/三种工厂模式介绍.html">
            
                <a href="../设计模式/factory/三种工厂模式介绍.html">
            
                    
                    三种工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.3" data-path="../设计模式/factory/实战工厂模式.html">
            
                <a href="../设计模式/factory/实战工厂模式.html">
            
                    
                    实战工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.4" data-path="../设计模式/factory/实战抽象工厂模式.html">
            
                <a href="../设计模式/factory/实战抽象工厂模式.html">
            
                    
                    实战抽象工厂模式
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">mysql篇</li>
        
        
    
        <li class="chapter " data-level="9.1" data-path="../数据库/mysql/1.b树b+树的底层原理.html">
            
                <a href="../数据库/mysql/1.b树b+树的底层原理.html">
            
                    
                    1.mysql索引基础之b树与b+树⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.2" data-path="../数据库/mysql/2.mysql索引.html">
            
                <a href="../数据库/mysql/2.mysql索引.html">
            
                    
                    2.mysql索引及优化⭐⭐⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.3" data-path="../数据库/mysql/3.mysql存储引擎.html">
            
                <a href="../数据库/mysql/3.mysql存储引擎.html">
            
                    
                    3.mysql存储引擎.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.4" data-path="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                <a href="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                    
                    4.多版本并发控制之mvcc原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.5" data-path="../数据库/mysql/4.mysql事务.html">
            
                <a href="../数据库/mysql/4.mysql事务.html">
            
                    
                    5.mysql事务
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.6" data-path="../数据库/mysql/5.mysql锁机制.html">
            
                <a href="../数据库/mysql/5.mysql锁机制.html">
            
                    
                    6.mysql的锁机制
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.7" data-path="../数据库/mysql/6.mysql面试题一.html">
            
                <a href="../数据库/mysql/6.mysql面试题一.html">
            
                    
                    7.mysql面试题一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高并发中间件篇</li>
        
        
    

    
        
        <li class="header">架构理论篇</li>
        
        
    
        <li class="chapter " data-level="11.1" data-path="../架构/0.架构演进.html">
            
                <a href="../架构/0.架构演进.html">
            
                    
                    1.架构演进
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="11.2" data-path="../架构/0.微服务架构与soa架构.html">
            
                <a href="../架构/0.微服务架构与soa架构.html">
            
                    
                    2.微服务架构与soa架构
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高可用系统篇</li>
        
        
    
        <li class="chapter " data-level="12.1" data-path="../高可用架构/1.限流.html">
            
                <a href="../高可用架构/1.限流.html">
            
                    
                    1.系统限流
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.2" data-path="../高可用系统/2.服务熔断.html">
            
                <a href="../高可用系统/2.服务熔断.html">
            
                    
                    2.服务熔断
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.3" data-path="../高可用系统/3.服务降级.html">
            
                <a href="../高可用系统/3.服务降级.html">
            
                    
                    3.服务降级
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">spring-cloud 微服务篇</li>
        
        
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >6.树论</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><ul><li><span class="title-icon "></span><a href="#&#x4E00;-adt&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><b></b>&#x4E00; ADT&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5B9A;&#x4E49;"><b></b>1.&#x5B9A;&#x4E49;</a></li><li><span class="title-icon "></span><a href="#2&#x4E3B;&#x8981;&#x51FD;&#x6570;"><b></b>2.&#x4E3B;&#x8981;&#x51FD;&#x6570;</a></li><li><span class="title-icon "></span><a href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;"><b></b>3.&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E8C;-&#x5B57;&#x5178;&#x6811;&#x524D;&#x7F00;&#x6811;"><b></b>&#x4E8C; &#x5B57;&#x5178;&#x6811;(&#x524D;&#x7F00;&#x6811;)</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5B9A;&#x4E49;_1"><b></b>1.&#x5B9A;&#x4E49;</a></li><li><span class="title-icon "></span><a href="#2&#x4E3B;&#x8981;&#x539F;&#x7406;"><b></b>2.&#x4E3B;&#x8981;&#x539F;&#x7406;</a></li><li><span class="title-icon "></span><a href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_1"><b></b>3.&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E09;-avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><b></b>&#x4E09; AVL&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5B9A;&#x4E49;_2"><b></b>1.&#x5B9A;&#x4E49;</a></li><li><span class="title-icon "></span><a href="#2&#x4E3B;&#x8981;&#x51FD;&#x6570;_1"><b></b>2.&#x4E3B;&#x8981;&#x51FD;&#x6570;</a></li><li><span class="title-icon "></span><a href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_2"><b></b>3.&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</a></li></ul><li><span class="title-icon "></span><a href="#&#x4E94;-&#x7EBF;&#x6BB5;&#x6811;"><b></b>&#x4E94; &#x7EBF;&#x6BB5;&#x6811;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;"><b></b>1.&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;</a></li><li><span class="title-icon "></span><a href="#2&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;"><b></b>2.&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;</a></li><li><span class="title-icon "></span><a href="#3&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;"><b></b>3.&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;</a></li><li><span class="title-icon "></span><a href="#4&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;"><b></b>4.&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;</a></li><li><span class="title-icon "></span><a href="#5&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;"><b></b>5.&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;</a></li></ul><li><span class="title-icon "></span><a href="#&#x516D;-&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;"><b></b>&#x516D; &#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;</a></li><li><span class="title-icon "></span><a href="#&#x4E03;-haffman&#x6811;"><b></b>&#x4E03; Haffman&#x6811;</a></li><ul><li><span class="title-icon "></span><a href="#1haffman&#x7F16;&#x7801;"><b></b>1.Haffman&#x7F16;&#x7801;</a></li></ul></ul></ul></div><a href="#" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h2 id="&#x4E00;-adt&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><a name="&#x4E00;-adt&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;" class="anchor-navigation-ex-anchor" href="#&#x4E00;-adt&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E00;-adt&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;" class="plugin-anchor" href="#&#x4E00;-adt&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E00; ADT&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</h2>
<h3 id="1&#x5B9A;&#x4E49;"><a name="1&#x5B9A;&#x4E49;" class="anchor-navigation-ex-anchor" href="#1&#x5B9A;&#x4E49;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5B9A;&#x4E49;" class="plugin-anchor" href="#1&#x5B9A;&#x4E49;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5B9A;&#x4E49;</h3>
<p> &#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF08;BST&#xFF09;&#x4E5F;&#x79F0;&#x4E8C;&#x53C9;&#x6392;&#x5E8F;&#x6811;&#x6216;&#x4E8C;&#x53C9;&#x67E5;&#x627E;&#x6811;</p>
<p>&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF1A;&#x4E00;&#x68F5;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x53EF;&#x4EE5;&#x4E3A;&#x7A7A;&#xFF1B;&#x5982;&#x679C;&#x4E0D;&#x4E3A;&#x7A7A;&#xFF0C;&#x6EE1;&#x8DB3;&#x4EE5;&#x4E0B;&#x6027;&#x8D28;&#xFF1A;</p>
<ol>
<li>&#x975E;&#x7A7A;<strong>&#x5DE6;&#x5B50;&#x6811;</strong>&#x7684;&#x6240;&#x6709;&#x952E;&#x503C;<strong>&#x5C0F;&#x4E8E;</strong>&#x5176;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x952E;&#x503C;</li>
<li>&#x975E;&#x7A7A;<strong>&#x53F3;&#x5B50;&#x6811;</strong>&#x7684;&#x6240;&#x6709;&#x952E;&#x503C;<strong>&#x5927;&#x4E8E;</strong>&#x5176;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x952E;&#x503C;</li>
<li>&#x5DE6;&#x3001;&#x53F3;&#x5B50;&#x6811;&#x90FD;&#x662F;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;</li>
</ol>
<p>&#x5217;&#x5982;:</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203104413.png" alt="image-20201203104412845"></p>
<h3 id="2&#x4E3B;&#x8981;&#x51FD;&#x6570;"><a name="2&#x4E3B;&#x8981;&#x51FD;&#x6570;" class="anchor-navigation-ex-anchor" href="#2&#x4E3B;&#x8981;&#x51FD;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x4E3B;&#x8981;&#x51FD;&#x6570;" class="plugin-anchor" href="#2&#x4E3B;&#x8981;&#x51FD;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x4E3B;&#x8981;&#x51FD;&#x6570;</h3>
<p><strong>1. &#x67E5;&#x627E;</strong></p>
<ul>
<li>&#x67E5;&#x627E;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x5982;&#x679C;&#x6811;&#x4E3A;&#x7A7A;&#xFF0C;&#x8FD4;&#x56DE; NULL</li>
<li>&#x82E5;&#x641C;&#x7D22;&#x6811;&#x4E0D;&#x4E3A;&#x7A7A;&#xFF0C;&#x5219;&#x6839;&#x7ED3;&#x70B9;&#x952E;&#x503C;&#x548C; X &#x8FDB;&#x884C;&#x6BD4;&#x8F83;&#xFF0C;&#x5E76;&#x8FDB;&#x884C;&#x4E0D;&#x540C;&#x5904;&#x7406;&#xFF1A;<ol>
<li>&#x82E5; X <strong>&#x5C0F;&#x4E8E;</strong>&#x6839;&#x7ED3;&#x70B9;&#x952E;&#x503C;&#xFF0C;&#x5728;<strong>&#x5DE6;&#x5B50;&#x6811;</strong>&#x4E2D;&#x7EE7;&#x7EED;&#x67E5;&#x627E;</li>
<li>&#x82E5; X <strong>&#x5927;&#x4E8E;</strong>&#x6839;&#x7ED3;&#x70B9;&#x952E;&#x503C;&#xFF0C;&#x5728;<strong>&#x53F3;&#x5B50;&#x6811;</strong>&#x4E2D;&#x7EE7;&#x7EED;&#x67E5;&#x627E;</li>
<li>&#x5982; X &#x7B49;&#x4E8E;&#x6839;&#x8282;&#x70B9;&#x952E;&#x503C;&#xFF0C;&#x67E5;&#x627E;&#x7ED3;&#x675F;&#xFF0C;&#x8FD4;&#x56DE;&#x6307;&#x5411;&#x6B64;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;</li>
</ol>
</li>
</ul>
<p><strong>2. &#x67E5;&#x627E;&#x6700;&#x5927;&#x548C;&#x6700;&#x5C0F;&#x5143;&#x7D20;</strong></p>
<ul>
<li><strong>&#x6700;&#x5927;&#x5143;&#x7D20;</strong>&#x4E00;&#x5B9A;&#x662F;&#x5728;&#x6811;&#x7684;<strong>&#x6700;&#x53F3;</strong>&#x5206;&#x652F;&#x7684;&#x7AEF;&#x7ED3;&#x70B9;&#x4E0A;</li>
<li><strong>&#x6700;&#x5C0F;&#x5143;&#x7D20;</strong>&#x4E00;&#x5B9A;&#x662F;&#x5728;&#x6811;&#x7684;<strong>&#x6700;&#x5DE6;</strong>&#x5206;&#x652F;&#x7684;&#x7AEF;&#x7ED3;&#x70B9;&#x4E0A;</li>
</ul>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203104457.png" alt=""></p>
<p><strong>3. &#x5220;&#x9664;</strong></p>
<p>&#x5220;&#x9664;&#x7684;&#x4E09;&#x79CD;&#x60C5;&#x51B5;&#xFF1A;</p>
<ol>
<li>&#x8981;&#x5220;&#x9664;&#x7684;&#x662F;<strong>&#x53F6;&#x7ED3;&#x70B9;</strong>&#xFF1A;&#x76F4;&#x63A5;&#x5220;&#x9664;&#xFF0C;&#x5E76;&#x5C06;&#x5176;&#x7236;&#x7ED3;&#x70B9;&#x6307;&#x9488;&#x7F6E;&#x4E3A; NULL</li>
<li>&#x8981;&#x5220;&#x9664;&#x7684;&#x7ED3;&#x70B9;<strong>&#x53EA;&#x6709;&#x4E00;&#x4E2A;&#x5B69;&#x5B50;</strong>&#x7ED3;&#x70B9;&#xFF1A;&#x5C06;&#x5176;&#x7236;&#x7ED3;&#x70B9;&#x7684;&#x6307;&#x9488;&#x6307;&#x5411;&#x8981;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x7684;&#x5B69;&#x5B50;&#x7ED3;&#x70B9;</li>
<li>&#x8981;&#x5220;&#x9664;&#x7684;&#x7ED3;&#x70B9;&#x6709;&#x5DE6;&#x3001;&#x53F3;&#x4E24;&#x68F5;&#x5B50;&#x6811;&#xFF1A;&#x7528;<strong>&#x53F3;&#x5B50;&#x6811;&#x7684;&#x6700;&#x5C0F;&#x5143;&#x7D20;</strong>&#x6216;<strong>&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x6700;&#x5927;&#x5143;&#x7D20;</strong>&#x66FF;&#x4EE3;&#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9;</li>
</ol>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203104544.gif" alt="img"></p>
<h3 id="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;"><a name="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;" class="anchor-navigation-ex-anchor" href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;" class="plugin-anchor" href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</h3>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;malloc.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">int</span> ElementType;
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> TreeNode *BinTree;
<span class="hljs-keyword">struct</span> TreeNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

<span class="hljs-comment">// &#x67E5;&#x627E;&#x9012;&#x5F52;&#x5B9E;&#x73B0; </span>
<span class="hljs-function">BinTree <span class="hljs-title">Find</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(!BST)  <span class="hljs-comment">// &#x5982;&#x679C;&#x6839;&#x7ED3;&#x70B9;&#x4E3A;&#x7A7A;&#xFF0C;&#x8FD4;&#x56DE; NULL </span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>; 
    <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data) <span class="hljs-comment">// &#x6BD4;&#x6839;&#x7ED3;&#x70B9;&#x5C0F;&#xFF0C;&#x53BB;&#x5DE6;&#x5B50;&#x6811;&#x67E5;&#x627E; </span>
        <span class="hljs-keyword">return</span> Find(X,BST-&gt;Left); 
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)  <span class="hljs-comment">// &#x6BD4;&#x6839;&#x7ED3;&#x70B9;&#x5927;&#xFF0C;&#x53BB;&#x53F3;&#x5B50;&#x6811;&#x67E5;&#x627E; </span>
        <span class="hljs-keyword">return</span> Find(X,BST-&gt;Right);
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data == X) <span class="hljs-comment">// &#x627E;&#x5230;&#x4E86; </span>
        <span class="hljs-keyword">return</span> BST;
}

<span class="hljs-comment">// &#x67E5;&#x627E;&#x975E;&#x9012;&#x5F52;&#x5B9E;&#x73B0;</span>
<span class="hljs-function">BinTree <span class="hljs-title">IterFind</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    <span class="hljs-keyword">while</span>(BST){
        <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data)
            BST = BST-&gt;Left;
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)  <span class="hljs-comment">// &#x6BD4;&#x6839;&#x7ED3;&#x70B9;&#x5927;&#xFF0C;&#x53BB;&#x53F3;&#x5B50;&#x6811;&#x67E5;&#x627E; </span>
            BST = BST-&gt;Right;
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data == X) <span class="hljs-comment">// &#x627E;&#x5230;&#x4E86; </span>
            <span class="hljs-keyword">return</span> BST;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;
} 

<span class="hljs-comment">// &#x67E5;&#x627E;&#x6700;&#x5C0F;&#x503C;&#x7684;&#x9012;&#x5F52;&#x5B9E;&#x73B0;</span>
<span class="hljs-function">BinTree <span class="hljs-title">FindMin</span><span class="hljs-params">(BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(!BST)    <span class="hljs-comment">// &#x5982;&#x679C;&#x4E3A;&#x7A7A;&#x4E86;&#xFF0C;&#x8FD4;&#x56DE; NULL </span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">NULL</span>;  
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Left)   <span class="hljs-comment">// &#x8FD8;&#x5B58;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x6CBF;&#x5DE6;&#x5206;&#x652F;&#x7EE7;&#x7EED;&#x67E5;&#x627E; </span>
        <span class="hljs-keyword">return</span> FindMin(BST-&gt;Left);
    <span class="hljs-keyword">else</span>  <span class="hljs-comment">// &#x627E;&#x5230;&#x4E86; </span>
        <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x67E5;&#x627E;&#x6700;&#x5927;&#x503C;&#x7684;&#x975E;&#x9012;&#x5F52;&#x5B9E;&#x73B0;</span>
<span class="hljs-function">BinTree <span class="hljs-title">FindMax</span><span class="hljs-params">(BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(BST)  <span class="hljs-comment">// &#x5982;&#x679C;&#x4E0D;&#x7A7A; </span>
        <span class="hljs-keyword">while</span>(BST-&gt;Right)   <span class="hljs-comment">// &#x53EA;&#x8981;&#x53F3;&#x5B50;&#x6811;&#x8FD8;&#x5B58;&#x5728; </span>
            BST = BST-&gt;Right;
    <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x63D2;&#x5165;</span>
<span class="hljs-function">BinTree <span class="hljs-title">Insert</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    <span class="hljs-keyword">if</span>(!BST){  <span class="hljs-comment">// &#x5982;&#x679C;&#x4E3A;&#x7A7A;&#xFF0C;&#x521D;&#x59CB;&#x5316;&#x8BE5;&#x7ED3;&#x70B9; </span>
        BST = (BinTree)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> TreeNode));
        BST-&gt;Data = X;
        BST-&gt;Left = <span class="hljs-literal">NULL</span>;
        BST-&gt;Right = <span class="hljs-literal">NULL</span>;
    }<span class="hljs-keyword">else</span>{ <span class="hljs-comment">// &#x4E0D;&#x4E3A;&#x7A7A; </span>
        <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data)  <span class="hljs-comment">// &#x5982;&#x679C;&#x5C0F;&#xFF0C;&#x6302;&#x5728;&#x5DE6;&#x8FB9; </span>
            BST-&gt;Left = Insert(X,BST-&gt;Left);
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)  <span class="hljs-comment">// &#x5982;&#x679C;&#x5927;&#xFF0C;&#x6302;&#x5728;&#x53F3;&#x8FB9; </span>
            BST-&gt;Right = Insert(X,BST-&gt;Right);
        <span class="hljs-comment">// &#x5982;&#x679C;&#x76F8;&#x7B49;&#xFF0C;&#x4EC0;&#x4E48;&#x90FD;&#x4E0D;&#x7528;&#x505A; </span>
    }
    <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x5220;&#x9664;</span>
<span class="hljs-function">BinTree <span class="hljs-title">Delete</span><span class="hljs-params">(ElementType X,BinTree BST)</span></span>{
    BinTree tmp;
    <span class="hljs-keyword">if</span>(!BST)
        <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x8981;&#x5220;&#x9664;&#x7684;&#x5143;&#x7D20;&#x672A;&#x627E;&#x5230;&quot;</span>;
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(X &lt; BST-&gt;Data)   <span class="hljs-comment">// X &#x6BD4;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x503C;&#x5C0F;&#xFF0C;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#x7EE7;&#x7EED;&#x67E5;&#x627E;&#x5220;&#x9664; </span>
        BST-&gt;Left = Delete(X,BST-&gt;Left);
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Data &lt; X)   <span class="hljs-comment">// X &#x6BD4;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x503C;&#x5927;&#xFF0C;&#x5728;&#x53F3;&#x5B50;&#x6811;&#x7EE7;&#x7EED;&#x67E5;&#x627E;&#x5220;&#x9664; </span>
        BST-&gt;Right = Delete(X,BST-&gt;Right);
    <span class="hljs-keyword">else</span>{  <span class="hljs-comment">//  &#x627E;&#x5230;&#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9; </span>
        <span class="hljs-keyword">if</span>(BST-&gt;Left &amp;&amp; BST-&gt;Right){  <span class="hljs-comment">// &#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x6709;&#x4FE9;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
            tmp = FindMin(BST-&gt;Right);   <span class="hljs-comment">// &#x627E;&#x5230;&#x53F3;&#x5B50;&#x6811;&#x4E2D;&#x503C;&#x6700;&#x5C0F;&#x7684;</span>
            BST-&gt;Data = tmp-&gt;Data;     <span class="hljs-comment">// &#x7528;&#x627E;&#x5230;&#x7684;&#x503C;&#x8986;&#x76D6;&#x5F53;&#x524D;&#x7ED3;&#x70B9; </span>
            BST-&gt;Right = Delete(tmp-&gt;Data,BST-&gt;Right);    <span class="hljs-comment">// &#x628A;&#x524D;&#x9762;&#x627E;&#x5230;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x6700;&#x5C0F;&#x503C;&#x7ED3;&#x70B9;&#x5220;&#x9664; </span>
        }<span class="hljs-keyword">else</span>{  <span class="hljs-comment">// &#x88AB;&#x5220;&#x9664;&#x7ED3;&#x70B9;&#x53EA;&#x6709;&#x4E00;&#x4E2A;&#x5B69;&#x5B50;&#x7ED3;&#x70B9;&#x6216;&#x6CA1;&#x6709;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
            tmp = BST;
            <span class="hljs-keyword">if</span>(!BST-&gt;Left &amp;&amp; !BST-&gt;Right)  <span class="hljs-comment">// &#x6CA1;&#x6709;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
                BST = <span class="hljs-literal">NULL</span>;
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(BST-&gt;Left &amp;&amp; !BST-&gt;Right)  <span class="hljs-comment">// &#x53EA;&#x6709;&#x5DE6;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
                BST = BST-&gt;Left;
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(!BST-&gt;Left &amp;&amp; BST-&gt;Right)  <span class="hljs-comment">// &#x53EA;&#x6709;&#x53F3;&#x5B69;&#x5B50;&#x7ED3;&#x70B9; </span>
                BST = BST-&gt;Right;
            <span class="hljs-built_in">free</span>(tmp);
        }
    }
    <span class="hljs-keyword">return</span> BST;
} 

<span class="hljs-comment">// &#x4E2D;&#x5E8F;&#x904D;&#x5386; </span>
<span class="hljs-function"><span class="hljs-keyword">void</span>  <span class="hljs-title">InOrderTraversal</span><span class="hljs-params">(BinTree BT)</span></span>{
    <span class="hljs-keyword">if</span>(BT){
        InOrderTraversal(BT-&gt;Left);  <span class="hljs-comment">// &#x8FDB;&#x5165;&#x5DE6;&#x5B50;&#x6811; </span>
        <span class="hljs-built_in">cout</span>&lt;&lt;BT-&gt;Data;  <span class="hljs-comment">// &#x6253;&#x5370;&#x6839; </span>
        InOrderTraversal(BT-&gt;Right);  <span class="hljs-comment">// &#x8FDB;&#x5165;&#x53F3;&#x5B50;&#x6811; </span>
    }
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    BinTree BST = <span class="hljs-literal">NULL</span>;
    BST = Insert(<span class="hljs-number">5</span>,BST); 
    BST = Insert(<span class="hljs-number">7</span>,BST); 
    BST = Insert(<span class="hljs-number">3</span>,BST); 
    BST = Insert(<span class="hljs-number">1</span>,BST); 
    BST = Insert(<span class="hljs-number">2</span>,BST); 
    BST = Insert(<span class="hljs-number">4</span>,BST); 
    BST = Insert(<span class="hljs-number">6</span>,BST); 
    BST = Insert(<span class="hljs-number">8</span>,BST); 
    BST = Insert(<span class="hljs-number">9</span>,BST); 
    <span class="hljs-comment">/*
                5
               /\
              3  7
             /\     /\
            1 4 6  8
            \      \
             2      9
    */</span>
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x662F;&#xFF1A;&quot;</span>; 
    InOrderTraversal(BST);
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-built_in">endl</span>;
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x67E5;&#x627E;&#x6700;&#x5C0F;&#x503C;&#x662F;&#xFF1A;&quot;</span>&lt;&lt;FindMin(BST)-&gt;Data&lt;&lt;<span class="hljs-built_in">endl</span>;
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x67E5;&#x627E;&#x6700;&#x5927;&#x503C;&#x662F;&#xFF1A;&quot;</span>&lt;&lt;FindMax(BST)-&gt;Data&lt;&lt;<span class="hljs-built_in">endl</span>; 
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x67E5;&#x627E;&#x503C;&#x4E3A;3&#x7684;&#x7ED3;&#x70B9;&#x5DE6;&#x5B50;&#x6811;&#x7ED3;&#x70B9;&#x503C;&#x4E3A;&#xFF1A;&quot;</span>&lt;&lt;Find(<span class="hljs-number">3</span>,BST)-&gt;Left-&gt;Data&lt;&lt;<span class="hljs-built_in">endl</span>;
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x67E5;&#x627E;&#x503C;&#x4E3A;7&#x7684;&#x7ED3;&#x70B9;&#x53F3;&#x5B50;&#x6811;&#x7ED3;&#x70B9;&#x503C;&#x4E3A;&#xFF1A;&quot;</span>&lt;&lt;IterFind(<span class="hljs-number">7</span>,BST)-&gt;Right-&gt;Data&lt;&lt;<span class="hljs-built_in">endl</span>;
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x5220;&#x9664;&#x503C;&#x4E3A;5&#x7684;&#x7ED3;&#x70B9;&quot;</span>&lt;&lt;<span class="hljs-built_in">endl</span>;
    Delete(<span class="hljs-number">5</span>,BST);
    <span class="hljs-comment">/*
                6
               /\
              3  7
             /\      \
            1 4    8
            \      \
             2      9
    */</span>
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;&#x4E2D;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x7ED3;&#x679C;&#x662F;&#xFF1A;&quot;</span>; 
    InOrderTraversal(BST);
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-built_in">endl</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>
<h2 id="&#x4E8C;-&#x5B57;&#x5178;&#x6811;&#x524D;&#x7F00;&#x6811;"><a name="&#x4E8C;-&#x5B57;&#x5178;&#x6811;&#x524D;&#x7F00;&#x6811;" class="anchor-navigation-ex-anchor" href="#&#x4E8C;-&#x5B57;&#x5178;&#x6811;&#x524D;&#x7F00;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E8C;-&#x5B57;&#x5178;&#x6811;&#x524D;&#x7F00;&#x6811;" class="plugin-anchor" href="#&#x4E8C;-&#x5B57;&#x5178;&#x6811;&#x524D;&#x7F00;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E8C; &#x5B57;&#x5178;&#x6811;(&#x524D;&#x7F00;&#x6811;)</h2>
<h3 id="1&#x5B9A;&#x4E49;_1"><a name="1&#x5B9A;&#x4E49;_1" class="anchor-navigation-ex-anchor" href="#1&#x5B9A;&#x4E49;_1"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5B9A;&#x4E49;" class="plugin-anchor" href="#1&#x5B9A;&#x4E49;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5B9A;&#x4E49;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203113034.png" alt="image-20201203113033913"></p>
<p>Trie&#x53C8;&#x88AB;&#x79F0;&#x4E3A;&#x524D;&#x7F00;&#x6811;&#x3001;&#x5B57;&#x5178;&#x6811;&#xFF0C;&#x6240;&#x4EE5;&#x5F53;&#x7136;&#x662F;&#x4E00;&#x68F5;&#x6811;&#x3002;&#x4E0A;&#x9762;&#x8FD9;&#x68F5;Trie&#x6811;&#x5305;&#x542B;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#x96C6;&#x5408;&#x662F;{in, inn, int, tea, ten, to}&#x3002;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x7F16;&#x53F7;&#x662F;&#x6211;&#x4EEC;&#x4E3A;&#x4E86;&#x63CF;&#x8FF0;&#x65B9;&#x4FBF;&#x52A0;&#x4E0A;&#x53BB;&#x7684;&#x3002;&#x6811;&#x4E2D;&#x7684;&#x6BCF;&#x4E00;&#x6761;&#x8FB9;&#x4E0A;&#x90FD;&#x6807;&#x8BC6;&#x6709;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x3002;&#x8FD9;&#x4E9B;&#x5B57;&#x7B26;&#x53EF;&#x4EE5;&#x662F;&#x4EFB;&#x610F;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x96C6;&#x4E2D;&#x7684;&#x5B57;&#x7B26;&#x3002;&#x6BD4;&#x5982;&#x5BF9;&#x4E8E;&#x90FD;&#x662F;&#x5C0F;&#x5199;&#x5B57;&#x6BCD;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#xFF0C;&#x5B57;&#x7B26;&#x96C6;&#x5C31;&#x662F;&#x2019;a&#x2019;-&#x2018;z&#x2019;&#xFF1B;&#x5BF9;&#x4E8E;&#x90FD;&#x662F;&#x6570;&#x5B57;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#xFF0C;&#x5B57;&#x7B26;&#x96C6;&#x5C31;&#x662F;&#x2019;0&#x2019;-&#x2018;9&#x2019;&#xFF1B;&#x5BF9;&#x4E8E;&#x4E8C;&#x8FDB;&#x5236;&#x5B57;&#x7B26;&#x4E32;&#xFF0C;&#x5B57;&#x7B26;&#x96C6;&#x5C31;&#x662F;0&#x548C;1&#x3002;</p>
<p>&#x6BD4;&#x5982;&#x4E0A;&#x56FE;&#x4E2D;3&#x53F7;&#x8282;&#x70B9;&#x5BF9;&#x5E94;&#x7684;&#x8DEF;&#x5F84;0123&#x4E0A;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#x662F;inn&#xFF0C;8&#x53F7;&#x8282;&#x70B9;&#x5BF9;&#x5E94;&#x7684;&#x8DEF;&#x5F84;0568&#x4E0A;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#x662F;ten&#x3002;&#x7EC8;&#x7ED3;&#x70B9;&#x4E0E;&#x96C6;&#x5408;&#x4E2D;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#x662F;&#x4E00;&#x4E00;&#x5BF9;&#x5E94;&#x7684;&#x3002;</p>
<h3 id="2&#x4E3B;&#x8981;&#x539F;&#x7406;"><a name="2&#x4E3B;&#x8981;&#x539F;&#x7406;" class="anchor-navigation-ex-anchor" href="#2&#x4E3B;&#x8981;&#x539F;&#x7406;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x4E3B;&#x8981;&#x539F;&#x7406;" class="plugin-anchor" href="#2&#x4E3B;&#x8981;&#x539F;&#x7406;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x4E3B;&#x8981;&#x539F;&#x7406;</h3>
<p>&#x4E0B;&#x9762;&#x6211;&#x4EEC;&#x6765;&#x8BB2;&#x4E00;&#x4E0B;&#x5BF9;&#x4E8E;&#x7ED9;&#x5B9A;&#x7684;&#x5B57;&#x7B26;&#x4E32;&#x96C6;&#x5408;{W1, W2, W3, &#x2026; WN}&#x5982;&#x4F55;&#x521B;&#x5EFA;&#x5BF9;&#x5E94;&#x7684;Trie&#x6811;&#x3002;&#x5176;&#x5B9E;&#x4E0A;Trie&#x6811;&#x7684;&#x521B;&#x5EFA;&#x662F;&#x4ECE;&#x53EA;&#x6709;&#x6839;&#x8282;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x901A;&#x8FC7;&#x4F9D;&#x6B21;&#x5C06;W1, W2, W3, &#x2026; WN&#x63D2;&#x5165;Trie&#x4E2D;&#x5B9E;&#x73B0;&#x7684;&#x3002;&#x6240;&#x4EE5;&#x5173;&#x952E;&#x5C31;&#x662F;&#x4E4B;&#x524D;&#x63D0;&#x5230;&#x7684;Trie&#x7684;&#x63D2;&#x5165;&#x64CD;&#x4F5C;&#x3002;
&#x5177;&#x4F53;&#x6765;&#x8BF4;&#xFF0C;Trie&#x4E00;&#x822C;&#x652F;&#x6301;&#x4E24;&#x4E2A;&#x64CD;&#x4F5C;&#xFF1A;
\1. Trie.insert(W)&#xFF1A;&#x7B2C;&#x4E00;&#x4E2A;&#x64CD;&#x4F5C;&#x662F;&#x63D2;&#x5165;&#x64CD;&#x4F5C;&#xFF0C;&#x5C31;&#x662F;&#x5C06;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x4E32;W&#x52A0;&#x5165;&#x5230;&#x96C6;&#x5408;&#x4E2D;&#x3002;
\2. Trie.search(S)&#xFF1A;&#x7B2C;&#x4E8C;&#x4E2A;&#x64CD;&#x4F5C;&#x662F;&#x67E5;&#x8BE2;&#x64CD;&#x4F5C;&#xFF0C;&#x5C31;&#x662F;&#x67E5;&#x8BE2;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x4E32;S&#x662F;&#x4E0D;&#x662F;&#x5728;&#x96C6;&#x5408;&#x4E2D;&#x3002;</p>
<p>&#x5047;&#x8BBE;&#x6211;&#x4EEC;&#x8981;&#x63D2;&#x5165;&#x5B57;&#x7B26;&#x4E32;&#x201D;in&#x201D;&#x3002;&#x6211;&#x4EEC;&#x4E00;&#x5F00;&#x59CB;&#x4F4D;&#x4E8E;&#x6839;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;0&#x53F7;&#x8282;&#x70B9;&#xFF0C;&#x6211;&#x4EEC;&#x7528;P=0&#x8868;&#x793A;&#x3002;&#x6211;&#x4EEC;&#x5148;&#x770B;P&#x662F;&#x4E0D;&#x662F;&#x6709;&#x4E00;&#x6761;&#x6807;&#x8BC6;&#x7740;i&#x7684;&#x8FDE;&#x5411;&#x5B50;&#x8282;&#x70B9;&#x7684;&#x8FB9;&#x3002;&#x6CA1;&#x6709;&#x8FD9;&#x6761;&#x8FB9;&#xFF0C;&#x4E8E;&#x662F;&#x6211;&#x4EEC;&#x5C31;&#x65B0;&#x5EFA;&#x4E00;&#x4E2A;&#x8282;&#x70B9;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;1&#x53F7;&#x8282;&#x70B9;&#xFF0C;&#x7136;&#x540E;&#x628A;1&#x53F7;&#x8282;&#x70B9;&#x8BBE;&#x7F6E;&#x4E3A;P&#x4E5F;&#x5C31;&#x662F;0&#x53F7;&#x8282;&#x70B9;&#x7684;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x5E76;&#x4E14;&#x5C06;&#x8FB9;&#x6807;&#x8BC6;&#x4E3A;i&#x3002;&#x6700;&#x540E;&#x6211;&#x4EEC;&#x79FB;&#x52A8;&#x5230;1&#x53F7;&#x8282;&#x70B9;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x4EE4;P=1&#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203113511.png" alt="image-20201203113511342"></p>
<p>&#x8FD9;&#x6837;&#x6211;&#x4EEC;&#x5C31;&#x628A;&#x201D;in&#x201D;&#x7684;i&#x5B57;&#x7B26;&#x63D2;&#x5165;&#x5230;Trie&#x4E2D;&#x4E86;&#x3002;&#x7136;&#x540E;&#x6211;&#x4EEC;&#x518D;&#x63D2;&#x5165;&#x5B57;&#x7B26;n&#xFF0C;&#x4E5F;&#x662F;&#x5148;&#x627E;P&#x4E5F;&#x5C31;&#x662F;1&#x53F7;&#x8282;&#x70B9;&#x6709;&#x6CA1;&#x6709;&#x6807;&#x8BB0;&#x4E3A;n&#x7684;&#x8FB9;&#x3002;&#x8FD8;&#x662F;&#x6CA1;&#x6709;&#xFF0C;&#x4E8E;&#x662F;&#x518D;&#x65B0;&#x5EFA;&#x4E00;&#x4E2A;&#x8282;&#x70B9;2&#xFF0C;&#x8BBE;&#x7F6E;&#x4E3A;P&#x4E5F;&#x5C31;&#x662F;1&#x53F7;&#x8282;&#x70B9;&#x7684;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x5E76;&#x4E14;&#x628A;&#x8FB9;&#x6807;&#x8BC6;&#x4E3A;n&#x3002;&#x6700;&#x540E;&#x518D;&#x79FB;&#x52A8;&#x5230;P=2&#x3002;&#x8FD9;&#x6837;&#x6211;&#x4EEC;&#x5C31;&#x628A;n&#x4E5F;&#x63D2;&#x5165;&#x4E86;&#x3002;&#x7531;&#x4E8E;n&#x662F;&#x201D;in&#x201D;&#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x8FD8;&#x9700;&#x8981;&#x5C06;P=2&#x8FD9;&#x4E2A;&#x8282;&#x70B9;&#x6807;&#x8BB0;&#x4E3A;&#x7EC8;&#x7ED3;&#x70B9;&#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203113526.png" alt="image-20201203113526242"></p>
<p>&#x73B0;&#x5728;&#x6211;&#x4EEC;&#x518D;&#x63D2;&#x5165;&#x5B57;&#x7B26;&#x4E32;&#x201D;inn&#x201D;&#x3002;&#x8FC7;&#x7A0B;&#x4E5F;&#x662F;&#x4E00;&#x6837;&#x7684;&#xFF0C;&#x4ECE;P=0&#x5F00;&#x59CB;&#x627E;&#x6807;&#x8BC6;&#x4E3A;i&#x7684;&#x8FB9;&#xFF0C;&#x8FD9;&#x6B21;&#x627E;&#x5230;1&#x53F7;&#x8282;&#x70B9;&#x3002;&#x4E8E;&#x662F;&#x6211;&#x4EEC;&#x5C31;&#x4E0D;&#x7528;&#x521B;&#x5EFA;&#x65B0;&#x8282;&#x70B9;&#x4E86;&#xFF0C;&#x76F4;&#x63A5;&#x79FB;&#x52A8;&#x5230;1&#x53F7;&#x8282;&#x70B9;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x4EE4;P=1&#x3002;&#x518D;&#x63D2;&#x5165;&#x5B57;&#x7B26;n&#xFF0C;&#x4E5F;&#x662F;&#x6709;2&#x53F7;&#x8282;&#x70B9;&#x5B58;&#x5728;&#xFF0C;&#x6240;&#x4EE5;&#x79FB;&#x52A8;&#x5230;2&#x53F7;&#x8282;&#x70B9;&#xFF0C;P=2&#x3002;&#x6700;&#x540E;&#x518D;&#x63D2;&#x5165;&#x5B57;&#x7B26;n&#x8FD9;&#x65F6;P&#x6CA1;&#x6709;&#x6807;&#x8BC6;&#x4E3A;n&#x7684;&#x8FB9;&#x4E86;&#xFF0C;&#x6240;&#x4EE5;&#x65B0;&#x5EFA;3&#x53F7;&#x8282;&#x70B9;&#x4F5C;&#x4E3A;2&#x53F7;&#x8282;&#x70B9;&#x7684;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x8FB9;&#x6807;&#x8BC6;&#x4E3A;n&#xFF0C;&#x540C;&#x65F6;&#x5C06;3&#x53F7;&#x8282;&#x70B9;&#x6807;&#x8BB0;&#x4E3A;&#x7EC8;&#x7ED3;&#x70B9;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203113541.png" alt="image-20201203113541749"></p>
<p>&#x5C06;&#x540E;&#x9762;&#x7684;&#x5B57;&#x7B26;&#x4E32;int tea ten to&#x90FD;&#x63D2;&#x5165;&#x4E4B;&#x540E;&#xFF0C;&#x5C31;&#x5F97;&#x5230;&#x4E86;&#x6211;&#x4EEC;&#x4E00;&#x5F00;&#x59CB;&#x7ED9;&#x51FA;&#x7684;Trie&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203113557.png" alt="image-20201203113557158"></p>
<h3 id="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_1"><a name="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_1" class="anchor-navigation-ex-anchor" href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_1"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;" class="plugin-anchor" href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</h3>
<p>&#x5B9A;&#x4E49;&#x7C7B; Trie</p>
<pre><code class="lang-C++"><span class="hljs-keyword">class</span> Trie {
<span class="hljs-keyword">private</span>:
    <span class="hljs-keyword">bool</span> isEnd;
    Trie* next[<span class="hljs-number">26</span>];
<span class="hljs-keyword">public</span>:
    <span class="hljs-comment">//&#x65B9;&#x6CD5;&#x5C06;&#x5728;&#x4E0B;&#x6587;&#x5B9E;&#x73B0;...</span>
};
</code></pre>
<p>&#x63D2;&#x5165;
&#x63CF;&#x8FF0;&#xFF1A;&#x5411; Trie &#x4E2D;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x5355;&#x8BCD; word</p>
<p>&#x5B9E;&#x73B0;&#xFF1A;&#x8FD9;&#x4E2A;&#x64CD;&#x4F5C;&#x548C;&#x6784;&#x5EFA;&#x94FE;&#x8868;&#x5F88;&#x50CF;&#x3002;&#x9996;&#x5148;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#x4E0E; word &#x7B2C;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x8FDB;&#x884C;&#x5339;&#x914D;&#xFF0C;&#x4E00;&#x76F4;&#x5339;&#x914D;&#x5230;&#x524D;&#x7F00;&#x94FE;&#x4E0A;&#x6CA1;&#x6709;&#x5BF9;&#x5E94;&#x7684;&#x5B57;&#x7B26;&#xFF0C;&#x8FD9;&#x65F6;&#x5F00;&#x59CB;&#x4E0D;&#x65AD;&#x5F00;&#x8F9F;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;&#x76F4;&#x5230;&#x63D2;&#x5165;&#x5B8C; word &#x7684;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x540C;&#x65F6;&#x8FD8;&#x8981;&#x5C06;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;isEnd = true;&#xFF0C;&#x8868;&#x793A;&#x5B83;&#x662F;&#x4E00;&#x4E2A;&#x5355;&#x8BCD;&#x7684;&#x672B;&#x5C3E;&#x3002;</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        <span class="hljs-keyword">if</span> (node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] == <span class="hljs-literal">NULL</span>) {
            node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] = <span class="hljs-keyword">new</span> Trie();
        }
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
    }
    node-&gt;isEnd = <span class="hljs-literal">true</span>;
}
</code></pre>
<p>&#x67E5;&#x627E;
&#x63CF;&#x8FF0;&#xFF1A;&#x67E5;&#x627E; Trie &#x4E2D;&#x662F;&#x5426;&#x5B58;&#x5728;&#x5355;&#x8BCD; word</p>
<p>&#x5B9E;&#x73B0;&#xFF1A;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x4E00;&#x76F4;&#x5411;&#x4E0B;&#x5339;&#x914D;&#x5373;&#x53EF;&#xFF0C;&#x5982;&#x679C;&#x51FA;&#x73B0;&#x7ED3;&#x70B9;&#x503C;&#x4E3A;&#x7A7A;&#x5C31;&#x8FD4;&#x56DE; false&#xFF0C;&#x5982;&#x679C;&#x5339;&#x914D;&#x5230;&#x4E86;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x90A3;&#x6211;&#x4EEC;&#x53EA;&#x9700;&#x5224;&#x65AD; node-&gt;isEnd&#x5373;&#x53EF;&#x3002;</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        node = node-&gt;next[c - <span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> node-&gt;isEnd;
}
</code></pre>
<p>&#x524D;&#x7F00;&#x5339;&#x914D;
&#x63CF;&#x8FF0;&#xFF1A;&#x5224;&#x65AD; Trie &#x4E2D;&#x662F;&#x6216;&#x6709;&#x4EE5; prefix &#x4E3A;&#x524D;&#x7F00;&#x7684;&#x5355;&#x8BCD;</p>
<p>&#x5B9E;&#x73B0;&#xFF1A;&#x548C; search &#x64CD;&#x4F5C;&#x7C7B;&#x4F3C;&#xFF0C;&#x53EA;&#x662F;&#x4E0D;&#x9700;&#x8981;&#x5224;&#x65AD;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#x7ED3;&#x70B9;&#x7684;isEnd&#xFF0C;&#x56E0;&#x4E3A;&#x65E2;&#x7136;&#x80FD;&#x5339;&#x914D;&#x5230;&#x6700;&#x540E;&#x4E00;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x90A3;&#x540E;&#x9762;&#x4E00;&#x5B9A;&#x6709;&#x5355;&#x8BCD;&#x662F;&#x4EE5;&#x5B83;&#x4E3A;&#x524D;&#x7F00;&#x7684;&#x3002;</p>
<p>C++</p>
<pre><code class="lang-c++"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">startsWith</span><span class="hljs-params">(<span class="hljs-built_in">string</span> prefix)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : prefix) {
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
}
&#x5230;&#x8FD9;&#x6211;&#x4EEC;&#x5C31;&#x5DF2;&#x7ECF;&#x5B9E;&#x73B0;&#x4E86;
</code></pre>
<p>&#x5BF9; Trie &#x7684;&#x4E00;&#x4E9B;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#xFF0C;&#x8FD9;&#x6837;&#x6211;&#x4EEC;&#x5BF9; Trie &#x5C31;&#x6709;&#x4E86;&#x8FDB;&#x4E00;&#x6B65;&#x7684;&#x7406;&#x89E3;&#x3002;&#x5B8C;&#x6574;&#x4EE3;&#x7801;&#x6211;&#x8D34;&#x5728;&#x4E86;&#x6587;&#x672B;&#x3002;</p>
<p>&#x603B;&#x7ED3;
&#x901A;&#x8FC7;&#x4EE5;&#x4E0A;&#x4ECB;&#x7ECD;&#x548C;&#x4EE3;&#x7801;&#x5B9E;&#x73B0;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x603B;&#x7ED3;&#x51FA; Trie &#x7684;&#x51E0;&#x70B9;&#x6027;&#x8D28;&#xFF1A;</p>
<p>Trie &#x7684;&#x5F62;&#x72B6;&#x548C;&#x5355;&#x8BCD;&#x7684;&#x63D2;&#x5165;&#x6216;&#x5220;&#x9664;&#x987A;&#x5E8F;&#x65E0;&#x5173;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#x5BF9;&#x4E8E;&#x4EFB;&#x610F;&#x7ED9;&#x5B9A;&#x7684;&#x4E00;&#x7EC4;&#x5355;&#x8BCD;&#xFF0C;Trie &#x7684;&#x5F62;&#x72B6;&#x90FD;&#x662F;&#x552F;&#x4E00;&#x7684;&#x3002;</p>
<p>&#x67E5;&#x627E;&#x6216;&#x63D2;&#x5165;&#x4E00;&#x4E2A;&#x957F;&#x5EA6;&#x4E3A; L &#x7684;&#x5355;&#x8BCD;&#xFF0C;&#x8BBF;&#x95EE; next &#x6570;&#x7EC4;&#x7684;&#x6B21;&#x6570;&#x6700;&#x591A;&#x4E3A; L+1&#xFF0C;&#x548C; Trie &#x4E2D;&#x5305;&#x542B;&#x591A;&#x5C11;&#x4E2A;&#x5355;&#x8BCD;&#x65E0;&#x5173;&#x3002;</p>
<p>Trie &#x7684;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x4E2D;&#x90FD;&#x4FDD;&#x7559;&#x7740;&#x4E00;&#x4E2A;&#x5B57;&#x6BCD;&#x8868;&#xFF0C;&#x8FD9;&#x662F;&#x5F88;&#x8017;&#x8D39;&#x7A7A;&#x95F4;&#x7684;&#x3002;&#x5982;&#x679C; Trie &#x7684;&#x9AD8;&#x5EA6;&#x4E3A; n&#xFF0C;&#x5B57;&#x6BCD;&#x8868;&#x7684;&#x5927;&#x5C0F;&#x4E3A; m&#xFF0C;&#x6700;&#x574F;&#x7684;&#x60C5;&#x51B5;&#x662F; Trie &#x4E2D;&#x8FD8;&#x4E0D;&#x5B58;&#x5728;&#x524D;&#x7F00;&#x76F8;&#x540C;&#x7684;&#x5355;&#x8BCD;&#xFF0C;&#x90A3;&#x7A7A;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x5C31;&#x4E3A; O(m^n)</p>
<p>&#x6700;&#x597D;&#x60C5;&#x51B5;&#x4E0B;,&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;O(m)</p>
<p>&#x6700;&#x540E;&#xFF0C;&#x5173;&#x4E8E; Trie &#x7684;&#x5E94;&#x7528;&#x573A;&#x666F;&#xFF0C;&#x5E0C;&#x671B;&#x4F60;&#x80FD;&#x8BB0;&#x4F4F; 8 &#x4E2A;&#x5B57;&#xFF1A;&#x4E00;&#x6B21;&#x5EFA;&#x6811;&#xFF0C;&#x591A;&#x6B21;&#x67E5;&#x8BE2;&#x3002;(&#x6162;&#x6162;&#x9886;&#x609F;&#x53ED;~~)</p>
<p>&#x5168;&#x90E8;&#x4EE3;&#x7801;</p>
<pre><code class="lang-c++">C++

<span class="hljs-keyword">class</span> Trie {
<span class="hljs-keyword">private</span>:
    <span class="hljs-keyword">bool</span> isEnd;
    Trie* next[<span class="hljs-number">26</span>];
<span class="hljs-keyword">public</span>:
    Trie() {
        isEnd = <span class="hljs-literal">false</span>;
        <span class="hljs-built_in">memset</span>(next, <span class="hljs-number">0</span>, <span class="hljs-keyword">sizeof</span>(next));
    }


<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">insert</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        <span class="hljs-keyword">if</span> (node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] == <span class="hljs-literal">NULL</span>) {
            node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>] = <span class="hljs-keyword">new</span> Trie();
        }
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
    }
    node-&gt;isEnd = <span class="hljs-literal">true</span>;
}

<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-built_in">string</span> word)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : word) {
        node = node-&gt;next[c - <span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> node-&gt;isEnd;
}

<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">startsWith</span><span class="hljs-params">(<span class="hljs-built_in">string</span> prefix)</span> </span>{
    Trie* node = <span class="hljs-keyword">this</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">char</span> c : prefix) {
        node = node-&gt;next[c-<span class="hljs-string">&apos;a&apos;</span>];
        <span class="hljs-keyword">if</span> (node == <span class="hljs-literal">NULL</span>) {
            <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
 }
};
</code></pre>
<h2 id="&#x4E09;-avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><a name="&#x4E09;-avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;" class="anchor-navigation-ex-anchor" href="#&#x4E09;-avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E09;-avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;" class="plugin-anchor" href="#&#x4E09;-avl&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E09; AVL&#x5E73;&#x8861;&#x4E8C;&#x53C9;&#x6811;</h2>
<h3 id="1&#x5B9A;&#x4E49;_2"><a name="1&#x5B9A;&#x4E49;_2" class="anchor-navigation-ex-anchor" href="#1&#x5B9A;&#x4E49;_2"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5B9A;&#x4E49;" class="plugin-anchor" href="#1&#x5B9A;&#x4E49;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5B9A;&#x4E49;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203105027.png" alt=""></p>
<h3 id="2&#x4E3B;&#x8981;&#x51FD;&#x6570;_1"><a name="2&#x4E3B;&#x8981;&#x51FD;&#x6570;_1" class="anchor-navigation-ex-anchor" href="#2&#x4E3B;&#x8981;&#x51FD;&#x6570;_1"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x4E3B;&#x8981;&#x51FD;&#x6570;" class="plugin-anchor" href="#2&#x4E3B;&#x8981;&#x51FD;&#x6570;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x4E3B;&#x8981;&#x51FD;&#x6570;</h3>
<p><strong>1.RR&#x5355;&#x65CB;</strong></p>
<p>&#x5F53;&quot;&#x63D2;&#x5165;&#x7ED3;&#x70B9;&quot;(BR)&#x662F;&quot;&#x88AB;&#x7834;&#x574F;&#x5E73;&#x8861;&#x7ED3;&#x70B9;&quot;(A)<strong>&#x53F3;&#x5B50;&#x6811;</strong>&#x7684;<strong>&#x53F3;&#x5B50;&#x6811;</strong>&#x65F6;&#xFF0C;&#x5373; RR &#x63D2;&#x5165;&#x65F6;&#xFF0C;&#x91C7;&#x7528; RR &#x65CB;&#x8F6C;&#x8C03;&#x6574;</p>
<p>&#x5176;&#x57FA;&#x672C;&#x601D;&#x8DEF;&#x662F;&#x628A; B &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x817E;&#x51FA;&#x6765;&#x6302;&#x5230; A &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A;&#xFF0C;&#x8FD4;&#x56DE; B &#x4F5C;&#x4E3A;&#x5F53;&#x524D;&#x5B50;&#x6811;&#x7684;&#x6839;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203105357.png" alt="image-20201203105357055"></p>
<pre><code class="lang-cpp"><span class="hljs-function">AVLTree <span class="hljs-title">RRRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    AVLTree B = A-&gt;right;   <span class="hljs-comment">// B &#x4E3A; A &#x7684;&#x53F3;&#x5B50;&#x6811;  </span>
    A-&gt;right = B-&gt;left;    <span class="hljs-comment">// B &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x6302;&#x5728; A &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A; </span>
    B-&gt;left = A;   <span class="hljs-comment">//  A &#x6302;&#x5728; B &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0A; </span>
    <span class="hljs-keyword">return</span> B;  <span class="hljs-comment">// &#x6B64;&#x65F6; B &#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x4E86;   </span>
}
</code></pre>
<p><strong>2.LL&#x5355;&#x65CB;</strong></p>
<p>&#x5F53;&quot;&#x63D2;&#x5165;&#x7ED3;&#x70B9;&quot;(BL)&#x662F;&quot;&#x88AB;&#x7834;&#x574F;&#x5E73;&#x8861;&#x7ED3;&#x70B9;&quot;(A)<strong>&#x5DE6;&#x5B50;&#x6811;</strong>&#x7684;<strong>&#x5DE6;&#x5B50;&#x6811;</strong>&#x65F6;&#xFF0C;&#x5373; LL &#x63D2;&#x5165;&#xFF0C;&#x91C7;&#x7528; RR &#x65CB;&#x8F6C;&#x8C03;&#x6574;</p>
<p>&#x5176;&#x57FA;&#x672C;&#x601D;&#x8DEF;&#x662F;&#x628A; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x817E;&#x51FA;&#x6765;&#x6302;&#x5230; A &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0A;&#xFF0C;&#x8FD4;&#x56DE; B &#x4F5C;&#x4E3A;&#x5F53;&#x524D;&#x5B50;&#x6811;&#x7684;&#x6839;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203105340.png" alt="image-20201203105340748"></p>
<pre><code class="lang-c++"><span class="hljs-function">AVLTree <span class="hljs-title">LLRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x6B64;&#x65F6;&#x6839;&#x8282;&#x70B9;&#x662F; A </span>
    AVLTree B = A-&gt;left;  <span class="hljs-comment">// B &#x4E3A; A &#x7684;&#x5DE6;&#x5B50;&#x6811;  </span>
    A-&gt;left = B-&gt;right;   <span class="hljs-comment">// B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x6302;&#x5728; A &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0A; </span>
    B-&gt;right = A;     <span class="hljs-comment">//  A &#x6302;&#x5728; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A; </span>
    <span class="hljs-keyword">return</span> B;  <span class="hljs-comment">// &#x6B64;&#x65F6; B &#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x4E86; </span>
}
</code></pre>
<p><strong>3.RL&#x53CC;&#x65CB;</strong></p>
<p>&#x5F53;&quot;&#x63D2;&#x5165;&#x7ED3;&#x70B9;&quot;(CL &#x6216;&#x8005; CR)&#x662F;&quot;&#x88AB;&#x7834;&#x574F;&#x5E73;&#x8861;&#x7ED3;&#x70B9;&quot;(A)<strong>&#x53F3;&#x5B50;&#x6811;</strong>&#x7684;<strong>&#x5DE6;&#x5B50;&#x6811;</strong>&#x65F6;&#xFF0C;&#x5373; RL &#x63D2;&#x5165;&#xFF0C;&#x91C7;&#x7528; RL &#x65CB;&#x8F6C;&#x8C03;&#x6574;</p>
<p>&#x57FA;&#x672C;&#x601D;&#x60F3;&#x662F;&#x5148;&#x5C06; B &#x4F5C;&#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x8FDB;&#x884C; <strong>LL &#x5355;&#x65CB;</strong>&#x8F6C;&#x5316;&#x4E3A; RR &#x63D2;&#x5165;&#xFF0C;&#x518D;&#x5C06; A &#x4F5C;&#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x8FDB;&#x884C; <strong>RR&#x5355;&#x65CB;</strong>&#xFF08;&#x5148; LL &#x518D; RR&#xFF09;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203105515.png" alt="image-20201203105515563"></p>
<pre><code class="lang-c++"><span class="hljs-function">AVLTree <span class="hljs-title">RLRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x5148; LL &#x5355;&#x65CB;</span>
    A-&gt;right = LLRotation(A-&gt;right);
    <span class="hljs-comment">// &#x518D; RR &#x5355;&#x65CB; </span>
    <span class="hljs-keyword">return</span> RRRotation(A); 
}
</code></pre>
<p><strong>4.LR&#x53CC;&#x65CB;&#x8F6C;</strong></p>
<p>&#x57FA;&#x672C;&#x601D;&#x60F3;&#x662F;&#x5148;&#x5C06; B &#x4F5C;&#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x8FDB;&#x884C; <strong>RR &#x5355;&#x65CB;</strong>&#x8F6C;&#x5316;&#x4E3A; LL &#x63D2;&#x5165;&#xFF0C;&#x518D;&#x5C06; A &#x4F5C;&#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x8FDB;&#x884C; <strong>LL &#x5355;&#x65CB;</strong>&#xFF08;&#x5148; RR &#x518D; LL&#xFF09;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203105636.png" alt="image-20201203105636347"></p>
<pre><code class="lang-c++"><span class="hljs-function">AVLTree <span class="hljs-title">LRRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x5148; RR &#x5355;&#x65CB;</span>
    A-&gt;left = RRRotation(A-&gt;left);
    <span class="hljs-comment">// &#x518D; LL &#x5355;&#x65CB; </span>
    <span class="hljs-keyword">return</span> LLRotation(A);
}
</code></pre>
<h3 id="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_2"><a name="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_2" class="anchor-navigation-ex-anchor" href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;_2"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;" class="plugin-anchor" href="#3&#x4EE3;&#x7801;&#x5B9E;&#x73B0;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x4EE3;&#x7801;&#x5B9E;&#x73B0;</h3>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">include</span><span class="hljs-meta-string">&lt;malloc.h&gt;</span></span>
<span class="hljs-keyword">typedef</span> <span class="hljs-keyword">struct</span> AVLNode *AVLTree;
<span class="hljs-keyword">struct</span> AVLNode{
    <span class="hljs-keyword">int</span> data;     <span class="hljs-comment">// &#x5B58;&#x503C; </span>
    AVLTree left;  <span class="hljs-comment">// &#x5DE6;&#x5B50;&#x6811; </span>
    AVLTree right;  <span class="hljs-comment">// &#x53F3;&#x5B50;&#x6811; </span>
    <span class="hljs-keyword">int</span> height;  <span class="hljs-comment">// &#x6811;&#x9AD8; </span>
};
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;

<span class="hljs-comment">// &#x8FD4;&#x56DE;&#x6700;&#x5927;&#x503C; </span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">Max</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b)</span></span>{
    <span class="hljs-keyword">return</span> a&gt;b?a:b;
}

<span class="hljs-comment">// &#x8FD4;&#x56DE;&#x6811;&#x9AD8;&#xFF0C;&#x7A7A;&#x6811;&#x8FD4;&#x56DE; -1 </span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getHeight</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-keyword">return</span> A==<span class="hljs-literal">NULL</span>?<span class="hljs-number">-1</span>:A-&gt;height;
}

<span class="hljs-comment">// LL&#x5355;&#x65CB;</span>
<span class="hljs-comment">// &#x628A; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x817E;&#x51FA;&#x6765;&#x6302;&#x7ED9; A &#x7684;&#x5DE6;&#x5B50;&#x6811;&#xFF0C;&#x518D;&#x5C06; A &#x6302;&#x5230; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A;&#x53BB; </span>
<span class="hljs-function">AVLTree <span class="hljs-title">LLRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x6B64;&#x65F6;&#x6839;&#x8282;&#x70B9;&#x662F; A </span>
    AVLTree B = A-&gt;left;  <span class="hljs-comment">// B &#x4E3A; A &#x7684;&#x5DE6;&#x5B50;&#x6811;  </span>
    A-&gt;left = B-&gt;right;   <span class="hljs-comment">// B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x6302;&#x5728; A &#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0A; </span>
    B-&gt;right = A;     <span class="hljs-comment">//  A &#x6302;&#x5728; B &#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0A; </span>
    A-&gt;height = Max(getHeight(A-&gt;left),getHeight(A-&gt;right)) + <span class="hljs-number">1</span>;
    B-&gt;height = Max(getHeight(B-&gt;left),A-&gt;height) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> B;  <span class="hljs-comment">// &#x6B64;&#x65F6; B &#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x4E86; </span>
}

<span class="hljs-comment">// RR&#x5355;&#x65CB;</span>
<span class="hljs-function">AVLTree <span class="hljs-title">RRRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x6B64;&#x65F6;&#x6839;&#x8282;&#x70B9;&#x662F; A </span>
    AVLTree B = A-&gt;right;
    A-&gt;right = B-&gt;left;
    B-&gt;left = A;
    A-&gt;height = Max(getHeight(A-&gt;left),getHeight(A-&gt;right)) + <span class="hljs-number">1</span>;
    B-&gt;height = Max(getHeight(B-&gt;left),A-&gt;height) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> B;  <span class="hljs-comment">// &#x6B64;&#x65F6; B &#x4E3A;&#x6839;&#x7ED3;&#x70B9;&#x4E86; </span>
}

<span class="hljs-comment">// LR&#x53CC;&#x65CB; </span>
<span class="hljs-function">AVLTree <span class="hljs-title">LRRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x5148; RR &#x5355;&#x65CB;</span>
    A-&gt;left = RRRotation(A-&gt;left);
    <span class="hljs-comment">// &#x518D; LL &#x5355;&#x65CB; </span>
    <span class="hljs-keyword">return</span> LLRotation(A);
}

<span class="hljs-comment">// RL&#x53CC;&#x65CB;</span>
<span class="hljs-function">AVLTree <span class="hljs-title">RLRotation</span><span class="hljs-params">(AVLTree A)</span></span>{
    <span class="hljs-comment">// &#x5148; LL &#x5355;&#x65CB;</span>
    A-&gt;right = LLRotation(A-&gt;right);
    <span class="hljs-comment">// &#x518D; RR &#x5355;&#x65CB; </span>
    <span class="hljs-keyword">return</span> RRRotation(A); 
}

<span class="hljs-function">AVLTree <span class="hljs-title">Insert</span><span class="hljs-params">(AVLTree T,<span class="hljs-keyword">int</span> x)</span></span>{
    <span class="hljs-keyword">if</span>(!T){  <span class="hljs-comment">// &#x5982;&#x679C;&#x8BE5;&#x7ED3;&#x70B9;&#x4E3A;&#x7A7A;&#xFF0C;&#x521D;&#x59CB;&#x5316;&#x7ED3;&#x70B9; </span>
        T = (AVLTree)<span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> AVLNode));
        T-&gt;data = x;
        T-&gt;left = <span class="hljs-literal">NULL</span>;
        T-&gt;right = <span class="hljs-literal">NULL</span>;
        T-&gt;height = <span class="hljs-number">0</span>;
    }<span class="hljs-keyword">else</span>{  <span class="hljs-comment">// &#x5426;&#x5219;&#x4E0D;&#x4E3A;&#x7A7A;&#xFF0C; </span>
        <span class="hljs-keyword">if</span>(x &lt; T-&gt;data){  <span class="hljs-comment">// &#x5DE6;&#x5B50;&#x6811; </span>
            T-&gt;left = Insert(T-&gt;left,x);
            <span class="hljs-keyword">if</span>(getHeight(T-&gt;left)-getHeight(T-&gt;right)==<span class="hljs-number">2</span>){  <span class="hljs-comment">// &#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x53F3;&#x5B50;&#x6811;&#x9AD8;&#x5EA6;&#x5DEE;&#x4E3A; 2 </span>
                <span class="hljs-keyword">if</span>(x &lt; T-&gt;left-&gt;data)  <span class="hljs-comment">// LL &#x5355;&#x65CB; </span>
                    T = LLRotation(T); 
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(T-&gt;left-&gt;data &lt; x)  <span class="hljs-comment">// LR&#x53CC;&#x65CB;</span>
                    T = LRRotation(T); 
            }
        }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(T-&gt;data &lt; x){
            T-&gt;right = Insert(T-&gt;right,x);
            <span class="hljs-keyword">if</span>(getHeight(T-&gt;right)-getHeight(T-&gt;left)==<span class="hljs-number">2</span>){
                <span class="hljs-keyword">if</span>(x &lt; T-&gt;right-&gt;data)  <span class="hljs-comment">// RL &#x53CC;&#x65CB; </span>
                    T = RLRotation(T); 
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(T-&gt;right-&gt;data &lt; x)  <span class="hljs-comment">// RR&#x5355;&#x65CB;</span>
                    T = RRRotation(T); 
            }
        }
    }
    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x6811;&#x9AD8; </span>
    T-&gt;height = Max(getHeight(T-&gt;left),getHeight(T-&gt;right)) + <span class="hljs-number">1</span>;
    <span class="hljs-keyword">return</span> T;
} 


<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    AVLTree T=<span class="hljs-literal">NULL</span>;
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">cin</span>&gt;&gt;n;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-keyword">int</span> tmp;
        <span class="hljs-built_in">cin</span>&gt;&gt;tmp;
        T = Insert(T,tmp);
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;T-&gt;data;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
}
</code></pre>
<p><strong>Sample Input :</strong></p>
<blockquote>
<p>7
88 70 61 96 120 90 65</p>
</blockquote>
<p><strong>Sample Output :</strong></p>
<blockquote>
<p>88</p>
</blockquote>
<h2 id="&#x4E94;-&#x7EBF;&#x6BB5;&#x6811;"><a name="&#x4E94;-&#x7EBF;&#x6BB5;&#x6811;" class="anchor-navigation-ex-anchor" href="#&#x4E94;-&#x7EBF;&#x6BB5;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E94;-&#x7EBF;&#x6BB5;&#x6811;" class="plugin-anchor" href="#&#x4E94;-&#x7EBF;&#x6BB5;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E94; &#x7EBF;&#x6BB5;&#x6811;</h2>
<h3 id="1&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;"><a name="1&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;" class="anchor-navigation-ex-anchor" href="#1&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;" class="plugin-anchor" href="#1&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x4EC0;&#x4E48;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#xFF1F;</h3>
<ul>
<li>&#x7EBF;&#x6BB5;&#x6811;&#x662F;&#x600E;&#x6837;&#x7684;&#x6811;&#x5F62;&#x7ED3;&#x6784;?</li>
</ul>
<p>&#x3000;&#x3000;&#x7EBF;&#x6BB5;&#x6811;&#x662F;&#x4E00;&#x79CD;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF0C;&#x4EC0;&#x4E48;&#x53EB;&#x505A;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF0C;&#x9996;&#x5148;&#x6EE1;&#x8DB3;&#x4E8C;&#x53C9;&#x6811;&#xFF0C;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5EA6;&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E;&#x4E8C;&#xFF0C;&#x5373;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x6700;&#x591A;&#x6709;&#x4E24;&#x9897;&#x5B50;&#x6811;&#xFF0C;&#x4F55;&#x4E3A;&#x641C;&#x7D22;&#xFF0C;&#x6211;&#x4EEC;&#x8981;&#x77E5;&#x9053;&#xFF0C;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x90FD;&#x5B58;&#x50A8;&#x4E86;&#x4E00;&#x4E2A;&#x533A;&#x95F4;&#xFF0C;&#x4E5F;&#x53EF;&#x4EE5;&#x7406;&#x89E3;&#x6210;&#x4E00;&#x4E2A;&#x7EBF;&#x6BB5;&#xFF0C;&#x800C;&#x641C;&#x7D22;&#xFF0C;&#x5C31;&#x662F;&#x5728;&#x8FD9;&#x4E9B;&#x7EBF;&#x6BB5;&#x4E0A;&#x8FDB;&#x884C;&#x641C;&#x7D22;&#x64CD;&#x4F5C;&#x5F97;&#x5230;&#x4F60;&#x60F3;&#x8981;&#x7684;&#x7B54;&#x6848;&#x3002;</p>
<ul>
<li>&#x7EBF;&#x6BB5;&#x6811;&#x80FD;&#x591F;&#x89E3;&#x51B3;&#x4EC0;&#x4E48;&#x6837;&#x7684;&#x95EE;&#x9898;&#x3002;</li>
</ul>
<p>&#x3000;&#x3000;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x9002;&#x7528;&#x8303;&#x56F4;&#x5F88;&#x5E7F;&#xFF0C;&#x53EF;&#x4EE5;&#x5728;&#x7EBF;&#x7EF4;&#x62A4;&#x4FEE;&#x6539;&#x4EE5;&#x53CA;&#x67E5;&#x8BE2;&#x533A;&#x95F4;&#x4E0A;&#x7684;&#x6700;&#x503C;&#xFF0C;&#x6C42;&#x548C;&#x3002;&#x66F4;&#x53EF;&#x4EE5;&#x6269;&#x5145;&#x5230;&#x4E8C;&#x7EF4;&#x7EBF;&#x6BB5;&#x6811;&#xFF08;&#x77E9;&#x9635;&#x6811;&#xFF09;&#x548C;&#x4E09;&#x7EF4;&#x7EBF;&#x6BB5;&#x6811;&#xFF08;&#x7A7A;&#x95F4;&#x6811;&#xFF09;&#x3002;&#x5BF9;&#x4E8E;&#x4E00;&#x7EF4;&#x7EBF;&#x6BB5;&#x6811;&#x6765;&#x8BF4;&#xFF0C;&#x6BCF;&#x6B21;&#x66F4;&#x65B0;&#x4EE5;&#x53CA;&#x67E5;&#x8BE2;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;O(logN)&#x3002;</p>
<ul>
<li>&#x7EBF;&#x6BB5;&#x6811;&#x548C;&#x5176;&#x4ED6;RMQ&#x7B97;&#x6CD5;&#x7684;&#x533A;&#x522B;</li>
</ul>
<p>&#x3000;&#x3000;&#x5E38;&#x7528;&#x7684;&#x89E3;&#x51B3;RMQ&#x95EE;&#x9898;&#x6709;ST&#x7B97;&#x6CD5;&#xFF0C;&#x4E8C;&#x8005;&#x9884;&#x5904;&#x7406;&#x65F6;&#x95F4;&#x90FD;&#x662F;O(NlogN)&#xFF0C;&#x800C;&#x4E14;ST&#x7B97;&#x6CD5;&#x7684;&#x5355;&#x6B21;&#x67E5;&#x8BE2;&#x64CD;&#x4F5C;&#x662F;O(1)&#xFF0C;&#x770B;&#x8D77;&#x6765;&#x6BD4;&#x7EBF;&#x6BB5;&#x6811;&#x597D;&#x591A;&#x4E86;&#xFF0C;&#x4F46;&#x4E8C;&#x8005;&#x7684;&#x533A;&#x522B;&#x5728;&#x4E8E;&#x7EBF;&#x6BB5;&#x6811;&#x652F;&#x6301;&#x5728;&#x7EBF;&#x66F4;&#x65B0;&#x503C;&#xFF0C;&#x800C;ST&#x7B97;&#x6CD5;&#x4E0D;&#x652F;&#x6301;&#x5728;&#x7EBF;&#x64CD;&#x4F5C;&#x3002;</p>
<p>&#x3000;&#x3000;&#x8FD9;&#x91CC;&#x4E5F;&#x5B58;&#x5728;&#x4E00;&#x4E2A;&#x8BEF;&#x533A;&#xFF0C;&#x521A;&#x5B66;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x65F6;&#x5019;&#x5C31;&#x4EE5;&#x4E3A;&#x7EBF;&#x6BB5;&#x6811;&#x548C;&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5DEE;&#x4E0D;&#x591A;&#xFF0C;&#x7528;&#x6765;&#x5904;&#x7406;RMQ&#x95EE;&#x9898;&#x548C;&#x6C42;&#x548C;&#x95EE;&#x9898;&#xFF0C;&#x4F46;&#x5176;&#x5B9E;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x529F;&#x80FD;&#x8FDC;&#x8FDC;&#x4E0D;&#x6B62;&#x8FD9;&#x4E9B;&#xFF0C;&#x6211;&#x4EEC;&#x8981;&#x719F;&#x7EC3;&#x7684;&#x7406;&#x89E3;&#x7EBF;&#x6BB5;&#x8FD9;&#x4E2A;&#x6982;&#x5FF5;&#x624D;&#x80FD;&#x66F4;&#x52A0;&#x6DF1;&#x5C42;&#x6B21;&#x7684;&#x7406;&#x89E3;&#x7EBF;&#x6BB5;&#x6811;&#x3002;</p>
<h3 id="2&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;"><a name="2&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;" class="anchor-navigation-ex-anchor" href="#2&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;" class="plugin-anchor" href="#2&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x5185;&#x5BB9;</h3>
<p>&#x3000;&#x3000;&#x73B0;&#x5728;&#x8BF7;&#x5404;&#x4F4D;&#x4E0D;&#x8981;&#x5E26;&#x7740;&#x7EBF;&#x6BB5;&#x6811;&#x53EA;&#x662F;&#x4E3A;&#x4E86;&#x89E3;&#x51B3;&#x533A;&#x95F4;&#x95EE;&#x9898;&#x7684;&#x6570;&#x636E;&#x7ED3;&#x6784;&#xFF0C;&#x4E8B;&#x5B9E;&#x4E0A;&#xFF0C;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#x591A;&#x7528;&#x4E8E;&#x89E3;&#x51B3;&#x533A;&#x95F4;&#x95EE;&#x9898;&#xFF0C;&#x5E76;&#x4E0D;&#x662F;&#x7EBF;&#x6BB5;&#x6811;&#x53EA;&#x80FD;&#x89E3;&#x51B3;&#x533A;&#x95F4;&#x95EE;&#x9898;&#xFF0C;&#x9996;&#x5148;&#xFF0C;&#x6211;&#x4EEC;&#x5F97;&#x5148;&#x660E;&#x767D;&#x51E0;&#x4EF6;&#x4E8B;&#x60C5;&#x3002;</p>
<p>&#x3000;&#x3000;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5B58;&#x4EC0;&#x4E48;&#xFF0C;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;&#x662F;&#x4EC0;&#x4E48;&#xFF0C;&#x5982;&#x4F55;&#x5EFA;&#x6811;&#x3002;</p>
<p>&#x3000;&#x3000;&#x4E0B;&#x9762;&#x6211;&#x4EE5;&#x4E00;&#x4E2A;&#x7B80;&#x5355;&#x7684;&#x533A;&#x95F4;&#x6700;&#x5927;&#x503C;&#x6765;&#x9610;&#x8FF0;&#x4E0A;&#x9762;&#x7684;&#x4E09;&#x4E2A;&#x6982;&#x5FF5;&#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203164449.png" alt="image-20201203164449399"></p>
<p>&#x3000;&#x3000;&#x5BF9;&#x4E8E;A[1:6] = {1,8,6,4,3,5}&#x6765;&#x8BF4;&#xFF0C;&#x7EBF;&#x6BB5;&#x6811;&#x5982;&#x4E0A;&#x6240;&#x793A;&#xFF0C;&#x7EA2;&#x8272;&#x4EE3;&#x8868;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5B58;&#x50A8;&#x7684;&#x533A;&#x95F4;&#xFF0C;&#x84DD;&#x8272;&#x4EE3;&#x8868;&#x8BE5;&#x533A;&#x95F4;&#x6700;&#x503C;&#x3002;</p>
<p>&#x3000;&#x3000;&#x53EF;&#x4EE5;&#x53D1;&#x73B0;&#xFF0C;<strong>&#x6BCF;&#x4E2A;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x503C;&#x5C31;&#x662F;&#x6570;&#x7EC4;&#x7684;&#x503C;&#xFF0C;&#x6BCF;&#x4E2A;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5EA6;&#x90FD;&#x4E3A;&#x4E8C;&#xFF0C;&#x4E14;&#x5DE6;&#x53F3;&#x4E24;&#x4E2A;&#x5B69;&#x5B50;&#x5206;&#x522B;&#x5B58;&#x50A8;&#x7236;&#x4EB2;&#x4E00;&#x534A;&#x7684;&#x533A;&#x95F4;&#x3002;&#x6BCF;&#x4E2A;&#x7236;&#x4EB2;&#x7684;&#x5B58;&#x50A8;&#x7684;&#x503C;&#x4E5F;&#x5C31;&#x662F;&#x4E24;&#x4E2A;&#x5B69;&#x5B50;&#x5B58;&#x50A8;&#x7684;&#x503C;&#x7684;&#x6700;&#x5927;&#x503C;&#x3002;</strong></p>
<p>&#x3000;&#x3000;&#x4E0A;&#x9762;&#x7684;&#x6BCF;&#x6761;&#x7ED3;&#x8BBA;&#x5E94;&#x8BE5;&#x90FD;&#x5BB9;&#x6613;&#x770B;&#x51FA;&#x6765;&#x3002;&#x90A3;&#x4E48;&#x7ED3;&#x70B9;&#x5230;&#x5E95;&#x662F;&#x5982;&#x4F55;&#x5B58;&#x50A8;&#x533A;&#x95F4;&#x7684;&#x5462;&#xFF0C;&#x4EE5;&#x53CA;&#x5982;&#x4F55;&#x5FEB;&#x901F;&#x627E;&#x5230;&#x975E;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#x7684;&#x5B69;&#x5B50;&#x4EE5;&#x53CA;&#x975E;&#x6839;&#x8282;&#x70B9;&#x7684;&#x7236;&#x4EB2;&#x5462;&#xFF0C;&#x8FD9;&#x91CC;&#x4E5F;&#x5C31;&#x662F;&#x7406;&#x89E3;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x91CD;&#x70B9;&#x4EE5;&#x53CA;&#x96BE;&#x70B9;&#x6240;&#x5728;&#xFF0C;&#x5982;&#x540C;&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x4F60;&#x7406;&#x89E3;&#x4E86;lowbit&#x5C31;&#x80FD;&#x5F88;&#x5FEB;&#x7406;&#x89E3;&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x4E00;&#x6837;&#xFF0C;&#x7EBF;&#x6BB5;&#x6811;&#x4F60;&#x53EA;&#x8981;&#x7406;&#x89E3;&#x4E86;&#x7ED3;&#x70B9;&#x4E0E;&#x7ED3;&#x70B9;&#x4E4B;&#x95F4;&#x7684;&#x5173;&#x7CFB;&#x4FBF;&#x80FD;&#x5F88;&#x5FEB;&#x7406;&#x89E3;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x77E5;&#x8BC6;&#x3002;</p>
<p>&#x3000;&#x3000;&#x5BF9;&#x4E8E;&#x4E00;&#x4E2A;&#x533A;&#x95F4;[l,r]&#x6765;&#x8BF4;&#xFF0C;&#x6700;&#x91CD;&#x8981;&#x7684;&#x6570;&#x636E;&#x5F53;&#x7136;&#x5C31;&#x662F;&#x533A;&#x95F4;&#x7684;&#x5DE6;&#x53F3;&#x7AEF;&#x70B9;l&#x548C;r&#xFF0C;&#x4F46;&#x662F;&#x5927;&#x90E8;&#x5206;&#x7684;&#x60C5;&#x51B5;&#x6211;&#x4EEC;&#x5E76;&#x4E0D;&#x4F1A;&#x53BB;&#x5B58;&#x50A8;&#x8FD9;&#x4E24;&#x4E2A;&#x6570;&#x503C;&#xFF0C;&#x800C;&#x662F;&#x901A;&#x8FC7;&#x9012;&#x5F52;&#x7684;&#x4F20;&#x53C2;&#x65B9;&#x5F0F;&#x8FDB;&#x884C;&#x4F20;&#x9012;&#x3002;&#x8FD9;&#x79CD;&#x65B9;&#x5F0F;&#x7528;&#x6307;&#x9488;&#x597D;&#x5B9E;&#x73B0;&#xFF0C;&#x5B9A;&#x4E49;&#x4E24;&#x4E2A;&#x5DE6;&#x53F3;&#x5B50;&#x6811;&#x9012;&#x5F52;&#x5373;&#x53EF;&#xFF0C;&#x4F46;&#x662F;&#x6307;&#x9488;&#x8868;&#x793A;&#x8FC7;&#x4E8E;&#x7E41;&#x7410;&#xFF0C;&#x800C;&#x4E14;&#x4E0D;&#x65B9;&#x4FBF;&#x5404;&#x79CD;&#x64CD;&#x4F5C;&#xFF0C;&#x5927;&#x90E8;&#x5206;&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x90FD;&#x662F;&#x4F7F;&#x7528;&#x6570;&#x7EC4;&#x8FDB;&#x884C;&#x8868;&#x793A;&#xFF0C;&#x90A3;&#x8FD9;&#x91CC;&#x600E;&#x4E48;&#x5FEB;&#x901F;&#x4F7F;&#x7528;&#x4E0B;&#x6807;&#x627E;&#x5230;&#x5DE6;&#x53F3;&#x5B50;&#x6811;&#x5462;&#x3002;</p>
<p>&#x3000;&#x3000;&#x5BF9;&#x4E8E;&#x4E0A;&#x8FF0;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x6211;&#x4EEC;&#x589E;&#x52A0;&#x7EFF;&#x8272;&#x6570;&#x5B57;&#x4E3A;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x4E0B;&#x6807;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203164458.png" alt="image-20201203164458708"></p>
<p>&#x3000;&#x3000;&#x5219;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;&#x5982;&#x4E0A;&#x6240;&#x793A;&#xFF0C;&#x8FD9;&#x91CC;&#x4F60;&#x53EF;&#x80FD;&#x4F1A;&#x95EE;&#xFF0C;&#x4E3A;&#x4EC0;&#x4E48;&#x6700;&#x4E0B;&#x4E00;&#x6392;&#x7684;&#x4E0B;&#x6807;&#x76F4;&#x63A5;&#x4ECE;9&#x8DF3;&#x5230;&#x4E86;12&#xFF0C;&#x9053;&#x7406;&#x4E5F;&#x5F88;&#x7B80;&#x5355;&#xFF0C;&#x4E2D;&#x95F4;&#x5176;&#x5B9E;&#x662F;&#x6709;&#x4E24;&#x4E2A;&#x7A7A;&#x95F4;&#x7684;&#x5440;&#xFF01;&#xFF01;&#x867D;&#x7136;&#x6CA1;&#x6709;&#x4F7F;&#x7528;&#xFF0C;&#x4F46;&#x662F;&#x4ED6;&#x5DF2;&#x7ECF;&#x5F00;&#x4E86;&#x4E24;&#x4E2A;&#x7A7A;&#x95F4;&#xFF0C;&#x8FD9;&#x4E5F;&#x662F;&#x4E3A;&#x4EC0;&#x4E48;&#x65E0;&#x4F18;&#x5316;&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x5EFA;&#x6811;&#x9700;&#x8981;2<em>2k&#xFF08;2k-1 &lt; n &lt; 2k)&#x7A7A;&#x95F4;&#xFF0C;&#x4E00;&#x822C;&#x4F1A;&#x5F00;&#x5230;4</em>n&#x7684;&#x7A7A;&#x95F4;&#x9632;&#x6B62;RE&#x3002;</p>
<p>&#x3000;&#x3000;&#x4ED4;&#x7EC6;&#x89C2;&#x5BDF;&#x6BCF;&#x4E2A;&#x7236;&#x4EB2;&#x548C;&#x5B69;&#x5B50;&#x4E0B;&#x6807;&#x7684;&#x5173;&#x7CFB;&#xFF0C;&#x6709;&#x53D1;&#x73B0;&#x4EC0;&#x4E48;&#x8054;&#x7CFB;&#x5417;&#xFF1F;&#x4E0D;&#x96BE;&#x53D1;&#x73B0;&#xFF0C;&#x6BCF;&#x4E2A;&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x4E0B;&#x6807;&#x90FD;&#x662F;&#x5076;&#x6570;&#xFF0C;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x4E0B;&#x6807;&#x90FD;&#x662F;&#x5947;&#x6570;&#x4E14;&#x4E3A;&#x5DE6;&#x5B50;&#x6811;&#x4E0B;&#x6807;+1&#xFF0C;&#x800C;&#x4E14;&#x4E0D;&#x96BE;&#x53D1;&#x73B0;&#x4EE5;&#x4E0B;&#x89C4;&#x5F8B;</p>
<ul>
<li>l = fa*2 &#xFF08;&#x5DE6;&#x5B50;&#x6811;&#x4E0B;&#x6807;&#x4E3A;&#x7236;&#x4EB2;&#x4E0B;&#x6807;&#x7684;&#x4E24;&#x500D;&#xFF09;</li>
<li>r = fa*2+1&#xFF08;&#x53F3;&#x5B50;&#x6811;&#x4E0B;&#x6807;&#x4E3A;&#x7236;&#x4EB2;&#x4E0B;&#x6807;&#x7684;&#x4E24;&#x500D;+1&#xFF09;</li>
</ul>
<p>&#x3000;&#x3000;&#x5177;&#x4F53;&#x8BC1;&#x660E;&#x4E5F;&#x5F88;&#x7B80;&#x5355;&#xFF0C;&#x628A;&#x7EBF;&#x6BB5;&#x6811;&#x770B;&#x6210;&#x4E00;&#x4E2A;&#x5B8C;&#x5168;&#x4E8C;&#x53C9;&#x6811;&#xFF08;&#x7A7A;&#x7ED3;&#x70B9;&#x4E5F;&#x5F53;&#x4F5C;&#x4F7F;&#x7528;&#xFF09;&#x5BF9;&#x4E8E;&#x4EFB;&#x610F;&#x4E00;&#x4E2A;&#x7ED3;&#x70B9;k&#x6765;&#x8BF4;&#xFF0C;&#x5B83;&#x6240;&#x5728;&#x6B64;&#x4E8C;&#x53C9;&#x6811;&#x7684;log2&#xFF08;k&#xFF09; &#x5C42;&#xFF0C;&#x5219;&#x6B64;&#x5C42;&#x5171;&#x6709;2log2(k)&#x4E2A;&#x7ED3;&#x70B9;&#xFF0C;&#x540C;&#x6837;&#x5BF9;&#x4E8E;k&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x90A3;&#x5C42;&#x6765;&#x8BF4;&#x6709;2log2(k)+1&#x4E2A;&#x7ED3;&#x70B9;&#xFF0C;&#x5219;&#x7ED3;&#x70B9;k&#x548C;&#x5DE6;&#x5B50;&#x6811;&#x95F4;&#x9694;&#x4E86;2<em>2log2(k)-k + 2</em>(k-2log2(k))&#x4E2A;&#x7ED3;&#x70B9;&#xFF0C;&#x7136;&#x540E;&#x8FD9;&#x5C31;&#x5F88;&#x7B80;&#x5355;&#x5C31;&#x5F97;&#x5230;k+2<em>2log2(k)-k + 2</em>(k-2log2(k)) = 2*k&#x7684;&#x5173;&#x7CFB;&#x4E86;&#x5427;&#xFF0C;&#x53F3;&#x5B50;&#x6811;&#x4E5F;&#x5C31;&#x7B49;&#x4E8E;&#x5DE6;&#x5B50;&#x6811;&#x7ED3;&#x70B9;+1&#x3002;</p>
<p>&#x3000;&#x3000;&#x662F;&#x4E0D;&#x662F;&#x89C9;&#x5F97;&#x5176;&#x5B9E;&#x5F88;&#x7B80;&#x5355;&#xFF0C;&#x800C;&#x4E14;&#x56E0;&#x4E3A;&#x5DE6;&#x5B50;&#x6811;&#x90FD;&#x662F;&#x5076;&#x6570;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x5E38;&#x7528;&#x4F4D;&#x8FD0;&#x7B97;&#x6765;&#x5BFB;&#x627E;&#x5DE6;&#x53F3;&#x5B50;&#x6811;</p>
<ul>
<li>k&lt;&lt;1&#xFF08;&#x7ED3;&#x70B9;k&#x7684;&#x5DE6;&#x5B50;&#x6811;&#x4E0B;&#x6807;&#xFF09;</li>
<li><p>k&lt;&lt;1|1&#xFF08;&#x7ED3;&#x70B9;k&#x7684;&#x53F3;&#x5B50;&#x6811;&#x4E0B;&#x6807;&#xFF09;</p>
<p>&#x3000;&#x6574;&#x7406;&#x4E00;&#x4E0B;&#x601D;&#x7EEA;&#xFF0C;&#x73B0;&#x5728;&#x5DF2;&#x7ECF;&#x660E;&#x767D;&#x4E86;&#x6570;&#x7EC4;&#x5982;&#x4F55;&#x5B58;&#x5728;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x7ED3;&#x70B9;&#x95F4;&#x7684;&#x5173;&#x7CFB;&#xFF0C;&#x4EE5;&#x53CA;&#x4F7F;&#x7528;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x5F0F;&#x5EFA;&#x7ACB;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x90A3;&#x4E48;&#x5177;&#x4F53;&#x5982;&#x4F55;&#x5EFA;&#x7ACB;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x6211;&#x4EEC;&#x6765;&#x770B;&#x4EE3;&#x7801;&#xFF0C;&#x4EE3;&#x7801;&#x4E2D;&#x4E0D;&#x6E05;&#x695A;&#x7684;&#x5730;&#x65B9;&#x90FD;&#x6709;&#x8BE6;&#x7EC6;&#x7684;&#x6CE8;&#x91CA;&#x8BF4;&#x660E;&#x3002;</p>
</li>
</ul>
<pre><code class="lang-c++"> <span class="hljs-number">1</span> <span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxn = <span class="hljs-number">1000</span>;
 <span class="hljs-number">2</span> <span class="hljs-keyword">int</span> a[maxn],t[maxn&lt;&lt;<span class="hljs-number">4</span>];        <span class="hljs-comment">//a&#x4E3A;&#x539F;&#x6765;&#x533A;&#x95F4;&#xFF0C;t&#x4E3A;&#x7EBF;&#x6BB5;&#x6811;</span>
 <span class="hljs-number">3</span> 
 <span class="hljs-number">4</span> <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Pushup</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span></span>{        <span class="hljs-comment">//&#x66F4;&#x65B0;&#x51FD;&#x6570;&#xFF0C;&#x8FD9;&#x91CC;&#x662F;&#x5B9E;&#x73B0;&#x6700;&#x5927;&#x503C; &#xFF0C;&#x540C;&#x7406;&#x53EF;&#x4EE5;&#x53D8;&#x6210;&#xFF0C;&#x6700;&#x5C0F;&#x503C;&#xFF0C;&#x533A;&#x95F4;&#x548C;&#x7B49;</span>
 <span class="hljs-number">5</span>     t[k] = max(t[k&lt;&lt;<span class="hljs-number">1</span>],t[k&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>]);
 <span class="hljs-number">6</span> }
 <span class="hljs-number">7</span> 
 <span class="hljs-number">8</span> <span class="hljs-comment">//&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x5EFA;&#x6811; build(1,1,n);</span>
 <span class="hljs-number">9</span> <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>{    <span class="hljs-comment">//k&#x4E3A;&#x5F53;&#x524D;&#x9700;&#x8981;&#x5EFA;&#x7ACB;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;l&#x4E3A;&#x5F53;&#x524D;&#x9700;&#x8981;&#x5EFA;&#x7ACB;&#x533A;&#x95F4;&#x7684;&#x5DE6;&#x7AEF;&#x70B9;&#xFF0C;r&#x5219;&#x4E3A;&#x53F3;&#x7AEF;&#x70B9;</span>
<span class="hljs-number">10</span>     <span class="hljs-keyword">if</span>(l == r)    <span class="hljs-comment">//&#x5DE6;&#x7AEF;&#x70B9;&#x7B49;&#x4E8E;&#x53F3;&#x7AEF;&#x70B9;&#xFF0C;&#x5373;&#x4E3A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x8D4B;&#x503C;&#x5373;&#x53EF;</span>
<span class="hljs-number">11</span>         t[k] = a[l];
<span class="hljs-number">12</span>     <span class="hljs-keyword">else</span>{
<span class="hljs-number">13</span>         <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
<span class="hljs-number">14</span>         build(k&lt;&lt;<span class="hljs-number">1</span>,l,m);    <span class="hljs-comment">//&#x9012;&#x5F52;&#x6784;&#x9020;&#x5DE6;&#x513F;&#x5B50;&#x7ED3;&#x70B9;</span>
<span class="hljs-number">15</span>         build(k&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>,m+<span class="hljs-number">1</span>,r);    <span class="hljs-comment">//&#x9012;&#x5F52;&#x6784;&#x9020;&#x53F3;&#x513F;&#x5B50;&#x7ED3;&#x70B9;</span>
<span class="hljs-number">16</span>         Pushup(k);    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;</span>
<span class="hljs-number">17</span>     }
<span class="hljs-number">18</span> }
</code></pre>
<p>&#x3000;&#x3000;&#x73B0;&#x5728;&#x518D;&#x6765;&#x770B;&#x4EE3;&#x7801;&#xFF0C;&#x662F;&#x4E0D;&#x662F;&#x89C9;&#x5F97;&#x6E05;&#x6670;&#x5F88;&#x591A;&#x4E86;&#xFF0C;&#x4F7F;&#x7528;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x6CD5;&#x5EFA;&#x7ACB;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x786E;&#x5B9E;&#x6E05;&#x6670;&#x6613;&#x61C2;&#xFF0C;&#x5404;&#x4F4D;&#x770B;&#x5230;&#x8FD9;&#x91CC;&#x4E5F;&#x8BF7;&#x81EA;&#x5DF1;&#x8BD5;&#x7740;&#x5B9E;&#x73B0;&#x4E00;&#x4E0B;&#x9012;&#x5F52;&#x5EFA;&#x6811;&#xFF0C;&#x82E5;&#x662F;&#x54EA;&#x91CC;&#x6709;&#x5361;&#x70B9;&#x518D;&#x6765;&#x770B;&#x4E00;&#x4E0B;&#x4EE3;&#x7801;&#x627E;&#x5230;&#x54EA;&#x91CC;&#x51FA;&#x4E86;&#x95EE;&#x9898;&#x3002;&#x90A3;&#x7EBF;&#x6BB5;&#x6811;&#x6709;&#x6CA1;&#x6709;&#x975E;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x5F0F;&#x5EFA;&#x6811;&#x5462;&#xFF0C;&#x7B54;&#x6848;&#x662F;&#x6709;&#xFF0C;&#x4F46;&#x662F;&#x975E;&#x9012;&#x5F52;&#x7684;&#x5EFA;&#x6811;&#x65B9;&#x5F0F;&#x4F1A;&#x4F7F;&#x5F97;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x67E5;&#x8BE2;&#x7B49;&#x64CD;&#x4F5C;&#x548C;&#x9012;&#x5F52;&#x5EFA;&#x6811;&#x65B9;&#x5F0F;&#x5B8C;&#x5168;&#x4E0D;&#x4E00;&#x6837;&#xFF0C;&#x7531;&#x7B80;&#x81F3;&#x96BE;&#xFF0C;&#x540E;&#x9762;&#x6211;&#x4EEC;&#x518D;&#x8BF4;&#x975E;&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x7684;&#x5B9E;&#x73B0;&#x3002;</p>
<p>&#x3000;&#x3000;&#x5230;&#x73B0;&#x5728;&#x4F60;&#x5E94;&#x8BE5;&#x53EF;&#x4EE5;&#x5EFA;&#x7ACB;&#x4E00;&#x9897;&#x7EBF;&#x6BB5;&#x6811;&#x4E86;&#xFF0C;&#x800C;&#x4E14;&#x77E5;&#x9053;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5B58;&#x50A8;&#x7684;&#x533A;&#x95F4;&#x548C;&#x503C;&#xFF0C;&#x5982;&#x679C;&#x4E0A;&#x8FF0;&#x64CD;&#x4F5C;&#x8FD8;&#x4E0D;&#x80FD;&#x5B9E;&#x73B0;&#x6216;&#x662F;&#x6709;&#x54EA;&#x91CC;&#x60F3;&#x4E0D;&#x660E;&#x767D;&#xFF0C;&#x5EFA;&#x8BAE;&#x518D;&#x7FFB;&#x56DE;&#x53BB;&#x770B;&#x4E00;&#x770B;&#x6240;&#x8BB2;&#x7684;&#x5185;&#x5BB9;&#x3002;&#x4E0D;&#x8981;&#x6025;&#x4E8E;&#x770B;&#x5B8C;&#xFF0C;&#x7406;&#x89E3;&#x624D;&#x66F4;&#x91CD;&#x8981;&#x3002;</p>
<h3 id="3&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;"><a name="3&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;" class="anchor-navigation-ex-anchor" href="#3&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;" class="plugin-anchor" href="#3&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x57FA;&#x672C;&#x64CD;&#x4F5C;</h3>
<p>&#x3000;&#x3000;&#x57FA;&#x672C;&#x64CD;&#x4F5C;&#x6709;&#x54EA;&#x4E9B;&#xFF0C;&#x4F60;&#x5E94;&#x8BE5;&#x4E5F;&#x80FD;&#x60F3;&#x51FA;&#x6765;&#xFF0C;&#x5728;&#x7EBF;&#x7684;&#x4E8C;&#x53C9;&#x641C;&#x7D22;&#x6811;&#xFF0C;&#x6240;&#x62E5;&#x6709;&#x7684;&#x64CD;&#x4F5C;&#x5F53;&#x7136;&#x6709;&#xFF0C;&#x66F4;&#x65B0;&#x548C;&#x8BE2;&#x95EE;&#x4E24;&#x79CD;&#x3002;</p>
<p><strong>1.&#x70B9;&#x66F4;&#x65B0;</strong></p>
<p>&#x3000;&#x3000;&#x5982;&#x4F55;&#x5B9E;&#x73B0;&#x70B9;&#x66F4;&#x65B0;&#xFF0C;&#x6211;&#x4EEC;&#x5148;&#x4E0D;&#x6025;&#x770B;&#x4EE3;&#x7801;&#xFF0C;&#x8FD8;&#x662F;&#x5BF9;&#x4E8E;&#x4E0A;&#x9762;&#x90A3;&#x4E2A;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x5047;&#x4F7F;&#x6211;&#x628A;a[3]+7&#xFF0C;&#x5219;&#x66F4;&#x65B0;&#x540E;&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x5E94;&#x8BE5;&#x53D8;&#x6210;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203164417.png" alt="image-20201203164417672"></p>
<p>&#x3000;&#x3000;&#x66F4;&#x65B0;&#x4E86;a[3]&#x540E;&#xFF0C;&#x5219;&#x6BCF;&#x4E2A;&#x5305;&#x542B;&#x6B64;&#x503C;&#x7684;&#x7ED3;&#x70B9;&#x90FD;&#x9700;&#x8981;&#x66F4;&#x65B0;&#xFF0C;&#x90A3;&#x4E48;&#x6709;&#x591A;&#x5C11;&#x4E2A;&#x7ED3;&#x70B9;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x5462;&#xFF1F;&#x6839;&#x636E;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x6027;&#x8D28;&#xFF0C;&#x4E0D;&#x96BE;&#x53D1;&#x73B0;&#x662F;log(k)&#x4E2A;&#x7ED3;&#x70B9;&#xFF0C;&#x8FD9;&#x4E5F;&#x6B63;&#x662F;&#x4E3A;&#x4EC0;&#x4E48;&#x6BCF;&#x6B21;&#x66F4;&#x65B0;&#x7684;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E3A;O(logN)&#xFF0C;&#x90A3;&#x5E94;&#x8BE5;&#x5982;&#x4F55;&#x5B9E;&#x73B0;&#x5462;&#xFF0C;&#x6211;&#x4EEC;&#x53D1;&#x73B0;&#xFF0C;&#x65E0;&#x8BBA;&#x4F60;&#x66F4;&#x65B0;&#x54EA;&#x4E2A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x6700;&#x7EC8;&#x90FD;&#x662F;&#x4F1A;&#x5230;&#x6839;&#x7ED3;&#x70B9;&#x7684;&#xFF0C;&#x800C;&#x628A;&#x8FD9;&#x4E2A;&#x5F80;&#x4E0A;&#x63A8;&#x7684;&#x8FC7;&#x7A0B;&#x9006;&#x8FC7;&#x6765;&#x5C31;&#x662F;&#x4ECE;&#x6839;&#x7ED3;&#x70B9;&#x5F00;&#x59CB;&#xFF0C;&#x627E;&#x5230;&#x5DE6;&#x5B50;&#x6811;&#x8FD8;&#x662F;&#x53F3;&#x5B50;&#x6811;&#x5305;&#x542B;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x5F80;&#x4E0B;&#x66F4;&#x65B0;&#x5373;&#x53EF;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x8FD8;&#x662F;&#x53EF;&#x4EE5;&#x4F7F;&#x7528;&#x9012;&#x5F52;&#x7684;&#x65B9;&#x6CD5;&#x5B9E;&#x73B0;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x70B9;&#x66F4;&#x65B0;</p>
<pre><code class="lang-c++"> <span class="hljs-number">1</span> <span class="hljs-comment">//&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x66F4;&#x65B0; updata(p,v,1,n,1);</span>
 <span class="hljs-number">2</span> <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">updata</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p,<span class="hljs-keyword">int</span> v,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> k)</span></span>{    <span class="hljs-comment">//p&#x4E3A;&#x4E0B;&#x6807;&#xFF0C;v&#x4E3A;&#x8981;&#x52A0;&#x4E0A;&#x7684;&#x503C;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;</span>
 <span class="hljs-number">3</span>     <span class="hljs-keyword">if</span>(l == r)    <span class="hljs-comment">//&#x5DE6;&#x7AEF;&#x70B9;&#x7B49;&#x4E8E;&#x53F3;&#x7AEF;&#x70B9;&#xFF0C;&#x5373;&#x4E3A;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x52A0;&#x4E0A;v&#x5373;&#x53EF;</span>
 <span class="hljs-number">4</span>         a[k] += v,t[k] += v;    <span class="hljs-comment">//&#x539F;&#x6570;&#x7EC4;&#x548C;&#x7EBF;&#x6BB5;&#x6811;&#x6570;&#x7EC4;&#x90FD;&#x5F97;&#x5230;&#x66F4;&#x65B0;</span>
 <span class="hljs-number">5</span>     <span class="hljs-keyword">else</span>{
 <span class="hljs-number">6</span>         <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
 <span class="hljs-number">7</span>         <span class="hljs-keyword">if</span>(p &lt;= m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#x533A;&#x95F4;</span>
 <span class="hljs-number">8</span>             updata(p,v,l,m,k&lt;&lt;<span class="hljs-number">1</span>);
 <span class="hljs-number">9</span>         <span class="hljs-keyword">else</span>    <span class="hljs-comment">//&#x5982;&#x679C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#x5728;&#x53F3;&#x5B50;&#x6811;&#x533A;&#x95F4;</span>
<span class="hljs-number">10</span>             updata(p,v,m+<span class="hljs-number">1</span>,r,k&lt;&lt;<span class="hljs-number">1</span>|<span class="hljs-number">1</span>);
<span class="hljs-number">11</span>         Pushup(k);    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;&#x7684;&#x503C;</span>
<span class="hljs-number">12</span>     }
<span class="hljs-number">13</span> }
</code></pre>
<p>&#x3000;&#x3000;&#x770B;&#x5B8C;&#x4EE3;&#x7801;&#x662F;&#x4E0D;&#x662F;&#x5F88;&#x6E05;&#x6670;&#xFF0C;&#x8FD9;&#x91CC;&#x4E5F;&#x5EFA;&#x8BAE;&#x81EA;&#x5DF1;&#x518D;&#x6B21;&#x624B;&#x52A8;&#x5B9E;&#x73B0;&#x4E00;&#x904D;&#x7406;&#x89E3;&#x9012;&#x5F52;&#x7684;&#x601D;&#x8DEF;&#x3002;</p>
<p><strong>2.&#x533A;&#x95F4;&#x67E5;&#x8BE2;</strong></p>
<p>&#x3000;&#x3000;&#x8BF4;&#x5B8C;&#x4E86;&#x5355;&#x70B9;&#x66F4;&#x65B0;&#x80AF;&#x5B9A;&#x5C31;&#x8981;&#x6765;&#x8BF4;&#x533A;&#x95F4;&#x67E5;&#x8BE2;&#x4E86;&#xFF0C;&#x6211;&#x4EEC;&#x77E5;&#x9053;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x6BCF;&#x4E2A;&#x7ED3;&#x70B9;&#x5B58;&#x50A8;&#x7684;&#x90FD;&#x662F;&#x4E00;&#x6BB5;&#x533A;&#x95F4;&#x7684;&#x4FE1;&#x606F; &#xFF0C;&#x5982;&#x679C;&#x6211;&#x4EEC;&#x521A;&#x597D;&#x8981;&#x67E5;&#x8BE2;&#x8FD9;&#x4E2A;&#x533A;&#x95F4;&#xFF0C;&#x90A3;&#x4E48;&#x5219;&#x76F4;&#x63A5;&#x8FD4;&#x56DE;&#x8FD9;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x4FE1;&#x606F;&#x5373;&#x53EF;&#xFF0C;&#x6BD4;&#x5982;&#x5BF9;&#x4E8E;&#x4E0A;&#x9762;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x5982;&#x679C;&#x6211;&#x76F4;&#x63A5;&#x67E5;&#x8BE2;[1,6]&#x8FD9;&#x4E2A;&#x533A;&#x95F4;&#x7684;&#x6700;&#x503C;&#xFF0C;&#x90A3;&#x4E48;&#x76F4;&#x63A5;&#x8FD4;&#x56DE;&#x6839;&#x8282;&#x70B9;&#x4FE1;&#x606F;&#x8FD4;&#x56DE;13&#x5373;&#x53EF;&#xFF0C;&#x4F46;&#x662F;&#x4E00;&#x822C;&#x6211;&#x4EEC;&#x4E0D;&#x4F1A;&#x51D1;&#x5DE7;&#x521A;&#x597D;&#x67E5;&#x8BE2;&#x90A3;&#x4E9B;&#x533A;&#x95F4;&#xFF0C;&#x6BD4;&#x5982;&#x73B0;&#x5728;&#x6211;&#x8981;&#x67E5;&#x8BE2;[2,5]&#x533A;&#x95F4;&#x7684;&#x6700;&#x503C;&#xFF0C;&#x8FD9;&#x65F6;&#x5019;&#x8BE5;&#x600E;&#x4E48;&#x529E;&#x5462;&#xFF0C;&#x6211;&#x4EEC;&#x6765;&#x770B;&#x770B;&#x54EA;&#x4E9B;&#x533A;&#x95F4;&#x662F;[2,5]&#x7684;&#x771F;&#x5B50;&#x96C6;&#xFF0C;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201203164422.png" alt="image-20201203164422697"></p>
<p>&#x3000;&#x3000;&#x4E00;&#x5171;&#x6709;5&#x4E2A;&#x533A;&#x95F4;&#xFF0C;&#x800C;&#x4E14;&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x53D1;&#x73B0;[4,5]&#x8FD9;&#x4E2A;&#x533A;&#x95F4;&#x5DF2;&#x7ECF;&#x5305;&#x542B;&#x4E86;&#x4E24;&#x4E2A;&#x5B50;&#x6811;&#x7684;&#x4FE1;&#x606F;&#xFF0C;&#x6240;&#x4EE5;&#x6211;&#x4EEC;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x53EA;&#x6709;&#x4E09;&#x4E2A;&#xFF0C;&#x5206;&#x522B;&#x662F;[2,2],[3,3],[4,5]&#xFF0C;&#x5230;&#x8FD9;&#x91CC;&#x4F60;&#x80FD;&#x901A;&#x8FC7;&#x66F4;&#x65B0;&#x7684;&#x601D;&#x8DEF;&#x60F3;&#x51FA;&#x6765;&#x67E5;&#x8BE2;&#x7684;&#x601D;&#x8DEF;&#x5417;? &#x6211;&#x4EEC;&#x8FD8;&#x662F;&#x4ECE;&#x6839;&#x8282;&#x70B9;&#x5F00;&#x59CB;&#x5F80;&#x4E0B;&#x9012;&#x5F52;&#xFF0C;&#x5982;&#x679C;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x662F;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x7684;&#x771F;&#x5B50;&#x96C6;&#xFF0C;&#x5219;&#x8FD4;&#x56DE;&#x8FD9;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x4FE1;&#x606F;&#x4E14;&#x4E0D;&#x9700;&#x8981;&#x518D;&#x5F80;&#x4E0B;&#x9012;&#x5F52;&#x4E86;&#xFF0C;&#x8FD9;&#x6837;&#x4ECE;&#x6839;&#x8282;&#x70B9;&#x5F80;&#x4E0B;&#x9012;&#x5F52;&#xFF0C;&#x65F6;&#x95F4;&#x590D;&#x6742;&#x5EA6;&#x4E5F;&#x662F;O(logN)&#x3002;&#x90A3;&#x4E48;&#x4EE3;&#x7801;&#x5219;&#x4E3A;</p>
<pre><code> 1 //&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x533A;&#x95F4;&#x67E5;&#x8BE2; query(L,R,1,n,1);
 2 int query(int L,int R,int l,int r,int k){    //[L,R]&#x5373;&#x4E3A;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;
 3     if(L &lt;= l &amp;&amp; r &lt;= R)    //&#x5982;&#x679C;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x7684;&#x533A;&#x95F4;&#x771F;&#x5305;&#x542B;&#x4E8E;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x5185;&#xFF0C;&#x5219;&#x8FD4;&#x56DE;&#x7ED3;&#x70B9;&#x4FE1;&#x606F;&#x4E14;&#x4E0D;&#x9700;&#x8981;&#x5F80;&#x4E0B;&#x9012;&#x5F52;
 4         return t[k];
 5     else{
 6         int res = -INF;    //&#x8FD4;&#x56DE;&#x503C;&#x53D8;&#x91CF;&#xFF0C;&#x6839;&#x636E;&#x5177;&#x4F53;&#x7EBF;&#x6BB5;&#x6811;&#x67E5;&#x8BE2;&#x7684;&#x4EC0;&#x4E48;&#x800C;&#x81EA;&#x5B9A;&#x4E49;
 7         int m = l + ((r-l)&gt;&gt;1);    //m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]
 8         if(L &lt;= m)    //&#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;
 9             res = max(res, query(L,R,l,m,k&lt;&lt;1));
10         if(R &gt; m)    //&#x5982;&#x679C;&#x53F3;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;&#xFF0C;&#x6CE8;&#x610F;&#x8FD9;&#x91CC;&#x4E0D;&#x662F;else if&#xFF0C;&#x56E0;&#x4E3A;&#x67E5;&#x8BE2;&#x533A;&#x95F4;&#x53EF;&#x80FD;&#x540C;&#x65F6;&#x548C;&#x5DE6;&#x53F3;&#x533A;&#x95F4;&#x90FD;&#x6709;&#x4EA4;&#x96C6;
11             res = max(res, query(L,R,m+1,r,k&lt;&lt;1|1));
12 
13         return res;    //&#x8FD4;&#x56DE;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x5F97;&#x5230;&#x7684;&#x4FE1;&#x606F;
14     }
15 }
</code></pre><p>&#x3000;&#x3000;&#x5982;&#x679C;&#x4F60;&#x80FD;&#x7406;&#x89E3;&#x5EFA;&#x6811;&#x548C;&#x66F4;&#x65B0;&#x7684;&#x8FC7;&#x7A0B;&#xFF0C;&#x90A3;&#x4E48;&#x8FD9;&#x91CC;&#x7684;&#x533A;&#x95F4;&#x67E5;&#x8BE2;&#x4E5F;&#x4E0D;&#x4F1A;&#x592A;&#x96BE;&#x7406;&#x89E3;&#x3002;&#x8FD8;&#x662F;&#x5EFA;&#x8BAE;&#x518D;&#x6B21;&#x624B;&#x52A8;&#x5B9E;&#x73B0;&#x3002;</p>
<p><strong>3.&#x533A;&#x95F4;&#x66F4;&#x65B0;</strong></p>
<p>&#x3000;&#x3000;&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x4E2D;&#x7684;&#x533A;&#x95F4;&#x66F4;&#x65B0;&#x6211;&#x4EEC;&#x7528;&#x4E86;&#x5DEE;&#x5206;&#x7684;&#x601D;&#x60F3;&#xFF0C;&#x800C;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x533A;&#x95F4;&#x66F4;&#x65B0;&#x76F8;&#x5BF9;&#x4E8E;&#x6811;&#x72B6;&#x6570;&#x7EC4;&#x5C31;&#x7A0D;&#x5FAE;&#x590D;&#x6742;&#x4E00;&#x70B9;&#xFF0C;&#x8FD9;&#x91CC;&#x6211;&#x4EEC;&#x5F15;&#x8FDB;&#x4E86;&#x4E00;&#x4E2A;&#x65B0;&#x4E1C;&#x897F;&#xFF0C;Lazy_tag&#xFF0C;&#x5B57;&#x9762;&#x610F;&#x601D;&#x5C31;&#x662F;&#x61D2;&#x60F0;&#x6807;&#x8BB0;&#x7684;&#x610F;&#x601D;&#xFF0C;&#x5B9E;&#x9645;&#x4E0A;&#x5B83;&#x7684;&#x529F;&#x80FD;&#x4E5F;&#x5C31;&#x662F;&#x5077;&#x61D2;= =&#xFF0C;&#x56E0;&#x4E3A;&#x5BF9;&#x4E8E;&#x4E00;&#x4E2A;&#x533A;&#x95F4;[L,R]&#x6765;&#x8BF4;&#xFF0C;&#x6211;&#x4EEC;&#x53EF;&#x80FD;&#x6BCF;&#x6B21;&#x90FD;&#x66F4;&#x65B0;&#x533A;&#x95F4;&#x4E2D;&#x7684;&#x6CA1;&#x4E2A;&#x503C;&#xFF0C;&#x90A3;&#x6837;&#x7684;&#x8BDD;&#x66F4;&#x65B0;&#x7684;&#x590D;&#x6742;&#x5EA6;&#x5C06;&#x4F1A;&#x662F;O(NlogN)&#xFF0C;&#x8FD9;&#x592A;&#x9AD8;&#x4E86;&#xFF0C;&#x6240;&#x4EE5;&#x5F15;&#x8FDB;&#x4E86;Lazy_tag&#xFF0C;&#x8FD9;&#x4E2A;&#x6807;&#x8BB0;&#x4E00;&#x822C;&#x7528;&#x4E8E;&#x5904;&#x7406;&#x7EBF;&#x6BB5;&#x6811;&#x7684;&#x533A;&#x95F4;&#x66F4;&#x65B0;&#x3002;
&#x3000;&#x3000;&#x7EBF;&#x6BB5;&#x6811;&#x5728;&#x8FDB;&#x884C;&#x533A;&#x95F4;&#x66F4;&#x65B0;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x4E3A;&#x4E86;&#x63D0;&#x9AD8;&#x66F4;&#x65B0;&#x7684;&#x6548;&#x7387;&#xFF0C;&#x6240;&#x4EE5;&#x6BCF;&#x6B21;&#x66F4;&#x65B0;&#x53EA;&#x66F4;&#x65B0;&#x5230;&#x66F4;&#x65B0;&#x533A;&#x95F4;&#x5B8C;&#x5168;&#x8986;&#x76D6;&#x7EBF;&#x6BB5;&#x6811;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;&#x6B62;&#xFF0C;&#x8FD9;&#x6837;&#x5C31;&#x4F1A;&#x5BFC;&#x81F4;&#x88AB;&#x66F4;&#x65B0;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x5B59;&#x7ED3;&#x70B9;&#x7684;&#x533A;&#x95F4;&#x5F97;&#x4E0D;&#x5230;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x4FE1;&#x606F;&#xFF0C;&#x6240;&#x4EE5;&#x5728;&#x88AB;&#x66F4;&#x65B0;&#x7ED3;&#x70B9;&#x4E0A;&#x6253;&#x4E0A;&#x4E00;&#x4E2A;&#x6807;&#x8BB0;&#xFF0C;&#x79F0;&#x4E3A;lazy-tag&#xFF0C;&#x7B49;&#x5230;&#x4E0B;&#x6B21;&#x8BBF;&#x95EE;&#x8FD9;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x7ED3;&#x70B9;&#x65F6;&#x518D;&#x5C06;&#x8FD9;&#x4E2A;&#x6807;&#x8BB0;&#x4F20;&#x9012;&#x7ED9;&#x5B50;&#x7ED3;&#x70B9;&#xFF0C;&#x6240;&#x4EE5;&#x4E5F;&#x53EF;&#x4EE5;&#x53EB;&#x5EF6;&#x8FDF;&#x6807;&#x8BB0;&#x3002;</p>
<p>&#x3000;&#x3000;&#x4E5F;&#x5C31;&#x662F;&#x8BF4;&#x9012;&#x5F52;&#x66F4;&#x65B0;&#x7684;&#x8FC7;&#x7A0B;&#xFF0C;&#x66F4;&#x65B0;&#x5230;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x533A;&#x95F4;&#x7684;&#x771F;&#x5B50;&#x96C6;&#x4E0D;&#x518D;&#x5F80;&#x4E0B;&#x66F4;&#x65B0;&#xFF0C;&#x4E0B;&#x6B21;&#x82E5;&#x662F;&#x9047;&#x5230;&#x9700;&#x8981;&#x7528;&#x8FD9;&#x4E0B;&#x9762;&#x7684;&#x7ED3;&#x70B9;&#x7684;&#x4FE1;&#x606F;&#xFF0C;&#x518D;&#x53BB;&#x66F4;&#x65B0;&#x8FD9;&#x4E9B;&#x7ED3;&#x70B9;&#xFF0C;&#x6240;&#x4EE5;&#x8FD9;&#x6837;&#x7684;&#x8BDD;&#x4F7F;&#x5F97;&#x533A;&#x95F4;&#x66F4;&#x65B0;&#x7684;&#x64CD;&#x4F5C;&#x548C;&#x533A;&#x95F4;&#x67E5;&#x8BE2;&#x7C7B;&#x4F3C;&#xFF0C;&#x590D;&#x6742;&#x5EA6;&#x4E3A;O(logN)&#x3002;</p>
<pre><code> 1 void Pushdown(int k){    //&#x66F4;&#x65B0;&#x5B50;&#x6811;&#x7684;lazy&#x503C;&#xFF0C;&#x8FD9;&#x91CC;&#x662F;RMQ&#x7684;&#x51FD;&#x6570;&#xFF0C;&#x8981;&#x5B9E;&#x73B0;&#x533A;&#x95F4;&#x548C;&#x7B49;&#x5219;&#x9700;&#x8981;&#x4FEE;&#x6539;&#x51FD;&#x6570;&#x5185;&#x5BB9;
 2     if(lazy[k]){    //&#x5982;&#x679C;&#x6709;lazy&#x6807;&#x8BB0;
 3         lazy[k&lt;&lt;1] += lazy[k];    //&#x66F4;&#x65B0;&#x5DE6;&#x5B50;&#x6811;&#x7684;lazy&#x503C;
 4         lazy[k&lt;&lt;1|1] += lazy[k];    //&#x66F4;&#x65B0;&#x53F3;&#x5B50;&#x6811;&#x7684;lazy&#x503C;
 5         t[k&lt;&lt;1] += lazy[k];        //&#x5DE6;&#x5B50;&#x6811;&#x7684;&#x6700;&#x503C;&#x52A0;&#x4E0A;lazy&#x503C;
 6         t[k&lt;&lt;1|1] += lazy[k];    //&#x53F3;&#x5B50;&#x6811;&#x7684;&#x6700;&#x503C;&#x52A0;&#x4E0A;lazy&#x503C;
 7         lazy[k] = 0;    //lazy&#x503C;&#x5F52;0
 8     }
 9 }
10 
11 //&#x9012;&#x5F52;&#x66F4;&#x65B0;&#x533A;&#x95F4; updata(L,R,v,1,n,1);
12 void updata(int L,int R,int v,int l,int r,int k){    //[L,R]&#x5373;&#x4E3A;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x533A;&#x95F4;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;
13     if(L &lt;= l &amp;&amp; r &lt;= R){    //&#x5982;&#x679C;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x7684;&#x533A;&#x95F4;&#x771F;&#x5305;&#x542B;&#x4E8E;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x533A;&#x95F4;&#x5185;
14         lazy[k] += v;    //&#x61D2;&#x60F0;&#x6807;&#x8BB0;
15         t[k] += v;    //&#x6700;&#x5927;&#x503C;&#x52A0;&#x4E0A;v&#x4E4B;&#x540E;&#xFF0C;&#x6B64;&#x533A;&#x95F4;&#x7684;&#x6700;&#x5927;&#x503C;&#x4E5F;&#x80AF;&#x5B9A;&#x662F;&#x52A0;v
16     }
17     else{
18         Pushdown(k);    //&#x91CD;&#x96BE;&#x70B9;&#xFF0C;&#x67E5;&#x8BE2;lazy&#x6807;&#x8BB0;&#xFF0C;&#x66F4;&#x65B0;&#x5B50;&#x6811;
19         int m = l + ((r-l)&gt;&gt;1);
20         if(L &lt;= m)    //&#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;
21             update(L,R,v,l,m,k&lt;&lt;1);
22         if(m &lt; R)    //&#x5982;&#x679C;&#x53F3;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;
23             update(L,R,v,m+1,r,k&lt;&lt;1|1);
24         Pushup(k);    //&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;
25     }
26 }
</code></pre><p>&#x3000;&#x3000;&#x6CE8;&#x610F;&#x770B;Pushdown&#x8FD9;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x5F53;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x67D0;&#x4E2A;&#x7ED3;&#x70B9;&#x7684;&#x5B50;&#x6811;&#x65F6;&#xFF0C;&#x9700;&#x8981;&#x7528;&#x5230;&#x8FD9;&#x4E2A;&#x51FD;&#x6570;&#xFF0C;&#x51FD;&#x6570;&#x529F;&#x80FD;&#x5C31;&#x662F;&#x66F4;&#x65B0;&#x5B50;&#x6811;&#x7684;lazy&#x503C;&#xFF0C;&#x53EF;&#x4EE5;&#x7406;&#x89E3;&#x4E3A;&#x5E73;&#x65F6;&#x5148;&#x628A;&#x4E8B;&#x60C5;&#x653E;&#x7740;&#xFF0C;&#x7B49;&#x5230;&#x54EA;&#x5929;&#x8981;&#x68C0;&#x67E5;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x5C31;&#x4E34;&#x65F6;&#x518D;&#x53BB;&#x505A;&#xFF0C;&#x800C;&#x4E14;&#x505A;&#x4E5F;&#x4E0D;&#x662F;&#x4E00;&#x6B21;&#x6027;&#x505A;&#x5B8C;&#xFF0C;&#x68C0;&#x67E5;&#x54EA;&#x4E00;&#x90E8;&#x5206;&#x5B83;&#x5C31;&#x53EA;&#x505A;&#x8FD9;&#x4E00;&#x90E8;&#x5206;&#x3002;&#x662F;&#x4E0D;&#x662F;&#x611F;&#x53D7;&#x5230;&#x4E86;&#x4EC0;&#x4E48;&#x662F;Lazy_tag&#xFF0C;&#x5B9E;&#x81F3;&#x540D;&#x5F52;= =&#x3002;</p>
<p>&#x3000;&#x3000;&#x503C;&#x5F97;&#x6CE8;&#x610F;&#x7684;&#x662F;&#xFF0C;&#x4F7F;&#x7528;&#x4E86;Lazy_tag&#x540E;&#xFF0C;&#x6211;&#x4EEC;&#x518D;&#x8FDB;&#x884C;&#x533A;&#x95F4;&#x67E5;&#x8BE2;&#x4E5F;&#x9700;&#x8981;&#x6539;&#x53D8;&#x3002;&#x533A;&#x95F4;&#x67E5;&#x8BE2;&#x7684;&#x4EE3;&#x7801;&#x5219;&#x53D8;&#x4E3A;</p>
<pre><code> 1 //&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x533A;&#x95F4;&#x67E5;&#x8BE2; query(L,R,1,n,1);
 2 int query(int L,int R,int l,int r,int k){    //[L,R]&#x5373;&#x4E3A;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;
 3     if(L &lt;= l &amp;&amp; r &lt;= R)    //&#x5982;&#x679C;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x7684;&#x533A;&#x95F4;&#x771F;&#x5305;&#x542B;&#x4E8E;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x5185;&#xFF0C;&#x5219;&#x8FD4;&#x56DE;&#x7ED3;&#x70B9;&#x4FE1;&#x606F;&#x4E14;&#x4E0D;&#x9700;&#x8981;&#x5F80;&#x4E0B;&#x9012;&#x5F52;
 4         return t[k];
 5     else{
 6         Pushdown(k);    /**&#x6BCF;&#x6B21;&#x90FD;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x5B50;&#x6811;&#x7684;Lazy&#x6807;&#x8BB0;*/
 7         int res = -INF;    //&#x8FD4;&#x56DE;&#x503C;&#x53D8;&#x91CF;&#xFF0C;&#x6839;&#x636E;&#x5177;&#x4F53;&#x7EBF;&#x6BB5;&#x6811;&#x67E5;&#x8BE2;&#x7684;&#x4EC0;&#x4E48;&#x800C;&#x81EA;&#x5B9A;&#x4E49;
 8         int mid = l + ((r-l)&gt;&gt;1);    //m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]
 9         if(L &lt;= m)    //&#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;
10             res = max(res, query(L,R,l,m,k&lt;&lt;1));
11         if(R &gt; m)    //&#x5982;&#x679C;&#x53F3;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;&#xFF0C;&#x6CE8;&#x610F;&#x8FD9;&#x91CC;&#x4E0D;&#x662F;else if&#xFF0C;&#x56E0;&#x4E3A;&#x67E5;&#x8BE2;&#x533A;&#x95F4;&#x53EF;&#x80FD;&#x540C;&#x65F6;&#x548C;&#x5DE6;&#x53F3;&#x533A;&#x95F4;&#x90FD;&#x6709;&#x4EA4;&#x96C6;
12             res = max(res, query(L,R,m+1,r,k&lt;&lt;1|1));
13 
14         return res;    //&#x8FD4;&#x56DE;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x5F97;&#x5230;&#x7684;&#x4FE1;&#x606F;
15     }
16 }
</code></pre><p>&#x3000;&#x3000;&#x5176;&#x5B9E;&#x53D8;&#x52A8;&#x4E5F;&#x4E0D;&#x5927;&#xFF0C;&#x5C31;&#x662F;&#x591A;&#x4E86;&#x4E00;&#x4E2A;&#x4E34;&#x65F6;&#x66F4;&#x65B0;&#x5B50;&#x6811;&#x7684;&#x503C;&#x7684;&#x8FC7;&#x7A0B;&#x3002;</p>
<h3 id="4&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;"><a name="4&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;" class="anchor-navigation-ex-anchor" href="#4&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;" class="plugin-anchor" href="#4&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x533A;&#x95F4;&#x6C42;&#x548C;&#x6A21;&#x677F;&#x4EE3;&#x7801;</h3>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> NumArray {
<span class="hljs-keyword">public</span>:
    <span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> ls k&lt;&lt;1</span>
    <span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> rs k&lt;&lt;1|1</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; t;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; lazy;
    <span class="hljs-keyword">int</span> n;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; nums;
    NumArray(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; nums) {;
        n=nums.size();
        <span class="hljs-keyword">if</span>(n==<span class="hljs-number">0</span>)<span class="hljs-keyword">return</span>;
        t=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        lazy=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n*<span class="hljs-number">4</span>,<span class="hljs-number">0</span>);
        <span class="hljs-keyword">this</span>-&gt;nums=nums;
        build(<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,n<span class="hljs-number">-1</span>);
    }

    <span class="hljs-comment">//push up</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushUp</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span></span>{
        t[k]=t[ls]+t[rs];
    }
    <span class="hljs-comment">//&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x5EFA;&#x6811;</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">build</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r)</span></span>{    <span class="hljs-comment">//k&#x4E3A;&#x5F53;&#x524D;&#x9700;&#x8981;&#x5EFA;&#x7ACB;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;l&#x4E3A;&#x5F53;&#x524D;&#x9700;&#x8981;&#x5EFA;&#x7ACB;&#x533A;&#x95F4;&#x7684;&#x5DE6;&#x7AEF;&#x70B9;&#xFF0C;r&#x5219;&#x4E3A;&#x53F3;&#x7AEF;&#x70B9;</span>
        <span class="hljs-keyword">if</span>(l == r)    <span class="hljs-comment">//&#x5DE6;&#x7AEF;&#x70B9;&#x7B49;&#x4E8E;&#x53F3;&#x7AEF;&#x70B9;&#xFF0C;&#x5373;&#x4E3A;&#x53F6;&#x5B50;&#x8282;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x8D4B;&#x503C;&#x5373;&#x53EF;</span>
            t[k] = nums[l];
        <span class="hljs-keyword">else</span>{
            <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
            build(ls,l,m);    <span class="hljs-comment">//&#x9012;&#x5F52;&#x6784;&#x9020;&#x5DE6;&#x513F;&#x5B50;&#x7ED3;&#x70B9;</span>
            build(rs,m+<span class="hljs-number">1</span>,r);    <span class="hljs-comment">//&#x9012;&#x5F52;&#x6784;&#x9020;&#x53F3;&#x513F;&#x5B50;&#x7ED3;&#x70B9;</span>
            pushUp(k);    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;</span>
        }
    }
    <span class="hljs-comment">//&#x70B9;&#x66F4;&#x65B0;</span>
    <span class="hljs-comment">//&#x9012;&#x5F52;&#x65B9;&#x5F0F;&#x66F4;&#x65B0; update_point(p,v,1,n,1);</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update_point</span><span class="hljs-params">(<span class="hljs-keyword">int</span> p, <span class="hljs-keyword">int</span> v, <span class="hljs-keyword">int</span> l, <span class="hljs-keyword">int</span> r, <span class="hljs-keyword">int</span> k)</span></span>{    <span class="hljs-comment">//p&#x4E3A;&#x4E0B;&#x6807;&#xFF0C;v&#x4E3A;&#x8981;&#x52A0;&#x4E0A;&#x7684;&#x503C;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;</span>
        <span class="hljs-keyword">if</span>(l == r)    <span class="hljs-comment">//&#x5DE6;&#x7AEF;&#x70B9;&#x7B49;&#x4E8E;&#x53F3;&#x7AEF;&#x70B9;&#xFF0C;&#x5373;&#x4E3A;&#x53F6;&#x5B50;&#x7ED3;&#x70B9;&#xFF0C;&#x76F4;&#x63A5;&#x52A0;&#x4E0A;v&#x5373;&#x53EF;</span>
            t[k] += v;    <span class="hljs-comment">//&#x7EBF;&#x6BB5;&#x6811;&#x6570;&#x7EC4;&#x90FD;&#x5F97;&#x5230;&#x66F4;&#x65B0;</span>
        <span class="hljs-keyword">else</span>{
            <span class="hljs-comment">//&#x5148;&#x5220;&#x9664;&#x6807;&#x8BB0;</span>
            pushdown(k);
            <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
            <span class="hljs-keyword">if</span>(p &lt;= m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#x5728;&#x5DE6;&#x5B50;&#x6811;&#x533A;&#x95F4;</span>
                update_point(p, v, l, m, ls);
            <span class="hljs-keyword">else</span>    <span class="hljs-comment">//&#x5982;&#x679C;&#x9700;&#x8981;&#x66F4;&#x65B0;&#x7684;&#x7ED3;&#x70B9;&#x5728;&#x53F3;&#x5B50;&#x6811;&#x533A;&#x95F4;</span>
                update_point(p, v, m + <span class="hljs-number">1</span>, r, rs);
            pushUp(k);    <span class="hljs-comment">//&#x66F4;&#x65B0;&#x7236;&#x8282;&#x70B9;&#x7684;&#x503C;</span>
        }
    }
    <span class="hljs-comment">//&#x533A;&#x95F4;&#x66F4;&#x65B0;</span>
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">pushdown</span><span class="hljs-params">(<span class="hljs-keyword">int</span> k)</span></span>{
        <span class="hljs-keyword">if</span>(lazy[k])
        {
            <span class="hljs-keyword">int</span> value=lazy[k];
            t[ls]+=value;
            t[rs]+=value;
            lazy[k]=<span class="hljs-number">0</span>;
            lazy[ls]+=value;
            lazy[rs]+=value;
        }
    }
    <span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update_range</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j,<span class="hljs-keyword">int</span> v,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> k)</span>
    </span>{
        <span class="hljs-keyword">if</span>(l&gt;=i&amp;&amp;r&lt;=j)
        {
            t[k]+=v;
            lazy[k]+=v;
        }
        <span class="hljs-keyword">else</span>
        {
            pushdown(k);
            <span class="hljs-keyword">int</span> mid=l+(r-l)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">if</span>(mid&gt;=i)
            {
               update_range(i,j,v,l,mid,ls);
            }
            <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(mid&lt;=j)
            {
                update_range(i,j,v,mid+<span class="hljs-number">1</span>,r,rs);
            }
            pushUp(k);
        }
    }
    <span class="hljs-comment">//&#x533A;&#x95F4;&#x67E5;&#x8BE2;</span>
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">range_sum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> L,<span class="hljs-keyword">int</span> R,<span class="hljs-keyword">int</span> l,<span class="hljs-keyword">int</span> r,<span class="hljs-keyword">int</span> k)</span></span>{    <span class="hljs-comment">//[L,R]&#x5373;&#x4E3A;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#xFF0C;l&#xFF0C;r&#x4E3A;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#xFF0C;k&#x4E3A;&#x7ED3;&#x70B9;&#x4E0B;&#x6807;</span>
        <span class="hljs-keyword">if</span>(L &lt;= l &amp;&amp; r &lt;= R)    <span class="hljs-comment">//&#x5982;&#x679C;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x7684;&#x533A;&#x95F4;&#x771F;&#x5305;&#x542B;&#x4E8E;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x5185;&#xFF0C;&#x5219;&#x8FD4;&#x56DE;&#x7ED3;&#x70B9;&#x4FE1;&#x606F;&#x4E14;&#x4E0D;&#x9700;&#x8981;&#x5F80;&#x4E0B;&#x9012;&#x5F52;</span>
            <span class="hljs-keyword">return</span> t[k];
        <span class="hljs-keyword">else</span>{
            pushdown(k);
            <span class="hljs-keyword">int</span> res = <span class="hljs-number">0</span>;    <span class="hljs-comment">//&#x8FD4;&#x56DE;&#x503C;&#x53D8;&#x91CF;&#xFF0C;&#x6839;&#x636E;&#x5177;&#x4F53;&#x7EBF;&#x6BB5;&#x6811;&#x67E5;&#x8BE2;&#x7684;&#x4EC0;&#x4E48;&#x800C;&#x81EA;&#x5B9A;&#x4E49;</span>
            <span class="hljs-keyword">int</span> m = l + ((r-l)&gt;&gt;<span class="hljs-number">1</span>);    <span class="hljs-comment">//m&#x5219;&#x4E3A;&#x4E2D;&#x95F4;&#x70B9;&#xFF0C;&#x5DE6;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[l,m],&#x53F3;&#x513F;&#x5B50;&#x7684;&#x7ED3;&#x70B9;&#x533A;&#x95F4;&#x4E3A;[m+1,r]</span>
            <span class="hljs-keyword">if</span>(L &lt;= m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x5DE6;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;</span>
                res += range_sum(L,R,l,m,ls);
            <span class="hljs-keyword">if</span>(R &gt; m)    <span class="hljs-comment">//&#x5982;&#x679C;&#x53F3;&#x5B50;&#x6811;&#x548C;&#x9700;&#x8981;&#x67E5;&#x8BE2;&#x7684;&#x533A;&#x95F4;&#x4EA4;&#x96C6;&#x975E;&#x7A7A;&#xFF0C;&#x6CE8;&#x610F;&#x8FD9;&#x91CC;&#x4E0D;&#x662F;else if&#xFF0C;&#x56E0;&#x4E3A;&#x67E5;&#x8BE2;&#x533A;&#x95F4;&#x53EF;&#x80FD;&#x540C;&#x65F6;&#x548C;&#x5DE6;&#x53F3;&#x533A;&#x95F4;&#x90FD;&#x6709;&#x4EA4;&#x96C6;</span>
                res += range_sum(L,R,m+<span class="hljs-number">1</span>,r,rs);
            <span class="hljs-keyword">return</span> res;    <span class="hljs-comment">//&#x8FD4;&#x56DE;&#x5F53;&#x524D;&#x7ED3;&#x70B9;&#x5F97;&#x5230;&#x7684;&#x4FE1;&#x606F;</span>
        }
    }
};
</code></pre>
<h3 id="5&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;"><a name="5&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;" class="anchor-navigation-ex-anchor" href="#5&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;" class="plugin-anchor" href="#5&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;"><i class="fa fa-link" aria-hidden="true"></i></a>5.&#x7EBF;&#x6BB5;&#x6811;&#x79BB;&#x6563;&#x5316;</h3>
<p>&#x5EFA;&#x7ACB;&#x4E00;&#x68F5;[1,1QW]&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#xFF0C;&#x5176;&#x6839;&#x7CFB;&#x662F;&#x975E;&#x5E38;&#x5E9E;&#x5927;&#x7684;&#xFF0C;TLE&#x548C;MLE&#x662F;&#x94C1;&#x5B9A;&#x7684;&#x4E86;&#x3002;&#x6240;&#x4EE5;&#x5FC5;&#x987B;&#x79BB;&#x6563;&#x5316;&#x3002;</p>
<p>&#x901A;&#x4FD7;&#x70B9;&#x8BF4;&#xFF0C;&#x79BB;&#x6563;&#x5316;&#x5C31;&#x662F;&#x538B;&#x7F29;&#x533A;&#x95F4;&#xFF0C;&#x4F7F;&#x539F;&#x6709;&#x7684;&#x957F;&#x533A;&#x95F4;&#x6620;&#x5C04;&#x5230;&#x65B0;&#x7684;&#x77ED;&#x533A;&#x95F4;&#xFF0C;&#x4F46;&#x662F;&#x533A;&#x95F4;&#x538B;&#x7F29;&#x524D;&#x540E;&#x7684;&#x8986;&#x76D6;&#x5173;&#x7CFB;&#x4E0D;&#x53D8;&#x3002;&#x4E3E;&#x4E2A;&#x4F8B;&#x5B50;&#xFF1A;</p>
<p>&#x6709;&#x4E00;&#x6761;1&#x5230;10&#x7684;&#x6570;&#x8F74;&#xFF08;&#x957F;&#x5EA6;&#x4E3A;9&#xFF09;&#xFF0C;&#x7ED9;&#x5B9A;4&#x4E2A;&#x533A;&#x95F4;[2,4] [3,6] [8,10] [6,9]&#xFF0C;&#x8986;&#x76D6;&#x5173;&#x7CFB;&#x5C31;&#x662F;&#x540E;&#x8005;&#x8986;&#x76D6;&#x524D;&#x8005;&#xFF0C;&#x6BCF;&#x4E2A;&#x533A;&#x95F4;&#x67D3;&#x8272;&#x4F9D;&#x6B21;&#x4E3A; 1 2 3 4&#x3002;</p>
<p>&#x73B0;&#x5728;&#x6211;&#x4EEC;&#x62BD;&#x53D6;&#x8FD9;4&#x4E2A;&#x533A;&#x95F4;&#x7684;8&#x4E2A;&#x7AEF;&#x70B9;&#xFF0C;2 4 3 6 8 10 6 9</p>
<p>&#x7136;&#x540E;&#x5220;&#x9664;&#x76F8;&#x540C;&#x7684;&#x7AEF;&#x70B9;&#xFF0C;&#x8FD9;&#x91CC;&#x76F8;&#x540C;&#x7684;&#x7AEF;&#x70B9;&#x4E3A;6&#xFF0C;&#x5219;&#x5269;&#x4E0B;2 4 3 6 8 10 9</p>
<p>&#x5BF9;&#x5176;&#x5347;&#x5E8F;&#x6392;&#x5E8F;&#xFF0C;&#x5F97;2 3 4 6 8 9 10</p>
<p>&#x7136;&#x540E;&#x5EFA;&#x7ACB;&#x6620;&#x5C04;</p>
<p>2   3   4   6   8   9  10</p>
<p>&#x2193;   &#x2193;   &#x2193;   &#x2193;   &#x2193;   &#x2193;   &#x2193;</p>
<p>1   2   3   4   5   6   7</p>
<p>&#x90A3;&#x4E48;&#x65B0;&#x7684;4&#x4E2A;&#x533A;&#x95F4;&#x4E3A; [1,3] [2,4] [5,7] [4,6]&#xFF0C;&#x8986;&#x76D6;&#x5173;&#x7CFB;&#x6CA1;&#x6709;&#x88AB;&#x6539;&#x53D8;&#x3002;&#x65B0;&#x6570;&#x8F74;&#x4E3A;1&#x5230;7&#xFF0C;&#x5373;&#x539F;&#x6570;&#x8F74;&#x7684;&#x957F;&#x5EA6;&#x4ECE;9&#x538B;&#x7F29;&#x5230;6&#xFF0C;&#x663E;&#x7136;&#x6784;&#x9020;[1,7]&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x6BD4;&#x6784;&#x9020;[1,10]&#x7684;&#x7EBF;&#x6BB5;&#x6811;&#x66F4;&#x7701;&#x7A7A;&#x95F4;&#xFF0C;&#x641C;&#x7D22;&#x4E5F;&#x66F4;&#x5FEB;&#xFF0C;&#x4F46;&#x662F;&#x6C42;&#x89E3;&#x7684;&#x7ED3;&#x679C;&#x5374;&#x662F;&#x4E00;&#x81F4;&#x7684;&#x3002;</p>
<p>&#x79BB;&#x6563;&#x5316;&#x65F6;&#x6709;&#x4E00;&#x70B9;&#x5FC5;&#x987B;&#x8981;&#x6CE8;&#x610F;&#x7684;&#xFF0C;&#x5C31;&#x662F;&#x5FC5;&#x987B;&#x5148;&#x5254;&#x9664;&#x76F8;&#x540C;&#x7AEF;&#x70B9;&#x540E;&#x518D;&#x6392;&#x5E8F;&#xFF0C;&#x8FD9;&#x6837;&#x53EF;&#x4EE5;&#x51CF;&#x5C11;&#x53C2;&#x4E0E;&#x6392;&#x5E8F;&#x5143;&#x7D20;&#x7684;&#x4E2A;&#x6570;&#xFF0C;&#x8282;&#x7701;&#x65F6;&#x95F4;&#x3002;</p>
<h2 id="&#x516D;-&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;"><a name="&#x516D;-&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;" class="anchor-navigation-ex-anchor" href="#&#x516D;-&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x516D;-&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;" class="plugin-anchor" href="#&#x516D;-&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x516D; &#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;</h2>
<p><strong>&#x4E3A;&#x4EC0;&#x4E48;&#x8981;&#x5BF9;&#x4E8C;&#x53C9;&#x6811;&#x8FDB;&#x884C;&#x7EBF;&#x7D22;&#x5316;&#xFF1F;</strong></p>
<blockquote>
<p>&#x5BF9;&#x4E8C;&#x53C9;&#x6811;&#x8FDB;&#x884C;&#x904D;&#x5386;&#x662F;&#x4EE5;&#x4E00;&#x5B9A;&#x7684;&#x89C4;&#x5219;&#x5C06;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x8282;&#x70B9;&#x6392;&#x5217;&#x6210;&#x4E00;&#x4E2A;&#x7EBF;&#x6027;&#x5E8F;&#x5217;&#xFF0C;&#x8FD9;&#x4E9B;&#x7EBF;&#x6027;&#x5E8F;&#x5217;&#x6709;&#x4E14;&#x4EC5;&#x6709;&#x4E00;&#x4E2A;&#x76F4;&#x63A5;&#x524D;&#x9A71;&#x548C;&#x76F4;&#x63A5;&#x540E;&#x7EE7;&#xFF0C;&#x4F46;&#x662F;&#x4EE5;&#x4E8C;&#x53C9;&#x94FE;&#x8868;&#x8FDB;&#x884C;&#x5B58;&#x50A8;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x53EA;&#x80FD;&#x627E;&#x5230;&#x8282;&#x70B9;&#x7684;&#x5DE6;&#x53F3;&#x5B69;&#x5B50;&#x4FE1;&#x606F;&#xFF0C;&#x4E0D;&#x80FD;&#x76F4;&#x63A5;&#x5F97;&#x5230;&#x8282;&#x70B9;&#x5728;&#x4EFB;&#x4E00;&#x5E8F;&#x5217;&#x7684;&#x524D;&#x9A71;&#x548C;&#x540E;&#x7EE7;&#x4FE1;&#x606F;&#xFF0C;&#x524D;&#x9A71;&#x548C;&#x540E;&#x7EE7;&#x4FE1;&#x606F;&#x53EA;&#x80FD;&#x5728;&#x904D;&#x5386;&#x7684;&#x52A8;&#x6001;&#x8FC7;&#x7A0B;&#x4E2D;&#x624D;&#x80FD;&#x5F97;&#x5230;&#x3002;</p>
</blockquote>
<p><strong>&#x5982;&#x4F55;&#x83B7;&#x53D6;&#x5230;&#x524D;&#x9A71;&#x548C;&#x540E;&#x7EE7;&#x7684;&#x4FE1;&#x606F;&#x5462;&#xFF1F;</strong></p>
<blockquote>
<p>&#x5728;&#x6709;n&#x4E2A;&#x8282;&#x70B9;&#x7684;&#x4E8C;&#x53C9;&#x94FE;&#x8868;&#x4E2D;&#x5FC5;&#x5B9A;&#x5B58;&#x5728;n+1&#x4E2A;&#x7A7A;&#x94FE;&#x57DF;&#xFF0C;&#x5229;&#x7528;&#x8FD9;&#x4E9B;&#x7A7A;&#x94FE;&#x57DF;&#x5B58;&#x653E;&#x8282;&#x70B9;&#x7684;&#x524D;&#x9A71;&#x548C;&#x540E;&#x7EE7;&#x4FE1;&#x606F;&#xFF0C;&#x6240;&#x4EE5;&#x5728;&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x4E0A;&#x589E;&#x52A0;&#x4E24;&#x4E2A;&#x6307;&#x9488;&#x57DF;&#x5206;&#x522B;&#x6307;&#x5411;&#x8282;&#x70B9;&#x5728;&#x4EFB;&#x4E00;&#x5E8F;&#x5217;&#x4E2D;&#x7684;&#x524D;&#x9A71;&#x548C;&#x540E;&#x7EE7;&#x4FE1;&#x606F;&#x3002;</p>
</blockquote>
<p>&#x8282;&#x70B9;&#x7ED3;&#x6784;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201205200903.png" alt="image-20201205200903303">png)</p>
<p>&#x4EE5;&#x4E0A;&#x8FF0;&#x8282;&#x70B9;&#x7ED3;&#x6784;&#x6784;&#x6210;&#x7684;&#x4E8C;&#x53C9;&#x94FE;&#x8868;&#x4F5C;&#x4E3A;&#x4E8C;&#x53C9;&#x94FE;&#x8868;&#x7684;&#x5B58;&#x50A8;&#x7ED3;&#x6784;&#xFF0C;&#x53EB;&#x505A;&#x7EBF;&#x7D22;&#x5316;&#x94FE;&#x8868;&#xFF1B;
&#x6307;&#x5411;&#x8282;&#x70B9;&#x524D;&#x9A71;&#x548C;&#x540E;&#x7EE7;&#x7684;&#x6307;&#x9488;&#x79F0;&#x4E3A;&#x7EBF;&#x7D22;&#xFF1B;
&#x52A0;&#x4E0A;&#x7EBF;&#x7D22;&#x7684;&#x4E8C;&#x53C9;&#x6811;&#x79F0;&#x4E3A;&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;&#xFF1B;
&#x5BF9;&#x4E8C;&#x53C9;&#x6811;&#x4EE5;&#x67D0;&#x79CD;&#x6B21;&#x5E8F;&#x904D;&#x5386;&#x4F7F;&#x5176;&#x6210;&#x4E3A;&#x7EBF;&#x7D22;&#x4E8C;&#x53C9;&#x6811;&#x7684;&#x8FC7;&#x7A0B;&#x79F0;&#x4E3A;&#x7EBF;&#x7D22;&#x5316;&#x3002;</p>
<p>&#x7EBF;&#x7D22;&#x5316;&#x7684;&#x603B;&#x601D;&#x8DEF;&#xFF1A;&#x5982;&#x679C;&#x8BBF;&#x95EE;&#x5230;&#x5F53;&#x524D;&#x8282;&#x70B9;&#x7684;&#x65F6;&#x5019;&#xFF0C;&#x7EBF;&#x7D22;&#x5316;&#x5176;&#x5DE6;&#x5B50;&#x6811;&#x5E76;&#x8BB0;&#x5F55;&#x4E0B;&#x4E0A;&#x4E00;&#x4E2A;&#x8BBF;&#x95EE;&#x7684;&#x8282;&#x70B9;&#xFF1B;&#x518D;&#x5BF9;&#x4E0A;&#x4E00;&#x4E2A;&#x8BBF;&#x95EE;&#x7684;&#x8282;&#x70B9;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x8FDB;&#x884C;&#x7EBF;&#x7D22;&#x5316;&#xFF0C;&#x76F4;&#x5230;&#x6240;&#x6709;&#x8282;&#x70B9;&#x90FD;&#x8BBF;&#x95EE;&#x5B8C;&#x3002;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201205200911.png" alt="image-20201205200911396"></p>
<pre><code>//prev&#x9700;&#x8981;&#x4F20;&#x5F15;&#x7528;&#x8FDB;&#x53BB;&#xFF0C;&#x624D;&#x80FD;&#x8BB0;&#x5F55;&#x4E0B;&#x4E0A;&#x6B21;&#x8BBF;&#x95EE;&#x7684;&#x8282;&#x70B9;&#xFF0C;&#x5426;&#x5219;&#x8282;&#x70B9;&#x7684;&#x53F3;&#x5B50;&#x6811;&#x7684;&#x7EBF;&#x7D22;&#x5316;&#x4E0D;&#x80FD;&#x5B8C;&#x6210;
void _PrevOrder_Th(Node* root, Node*&amp; prev)
    {
        if (root == NULL)
        {
            return;
        }
        if (root-&gt;_LeftNode == NULL)
        {
            root-&gt;_LeftNode = prev;
            root-&gt;LeftTag = THREAD;
        }
        if (prev&amp;&amp;prev-&gt;_RightNode == NULL)
        {
            prev-&gt;_RightNode = root;
            prev-&gt;RightTag = THREAD;
        }

        prev = root;
        if (root-&gt;LeftTag == LINK)
        {
            _PrevOrder_Th(root-&gt;_LeftNode, prev);
        }
        if (root-&gt;RightTag == LINK)
        {
            _PrevOrder_Th(root-&gt;_RightNode, prev);
        }
    }
</code></pre><p>&#x524D;&#x5E8F;&#x7EBF;&#x7D22;&#x5316;&#x7684;&#x904D;&#x5386;&#xFF1A;
&#x9047;&#x5230;&#x5148;&#x5BF9;&#x5176;&#x8FDB;&#x884C;&#x8FDB;&#x884C;&#x8BBF;&#x95EE;&#xFF0C;&#x518D;&#x5BF9;&#x5176;&#x5DE6;&#x5B50;&#x6811;&#x8FDB;&#x884C;&#x904D;&#x5386;&#x8BBF;&#x95EE;&#xFF0C;&#x76F4;&#x5230;&#x627E;&#x5230;&#x6700;&#x5DE6;&#x7684;&#x90A3;&#x4E2A;&#x8282;&#x70B9;&#xFF1B;&#x518D;&#x6839;&#x636E;&#x7EBF;&#x7D22;&#x5316;&#x7684;&#x6307;&#x5411;&#x5BF9;&#x5176;&#x53F3;&#x5B50;&#x6811;&#x8FDB;&#x884C;&#x904D;&#x5386;&#x8BBF;&#x95EE;&#x3002;</p>
<pre><code>void PreOrder()
    {
        Node* cur = _root;
        while (cur)
        {
            while (cur-&gt;LeftTag == LINK)
            {
                cout &lt;&lt; cur-&gt;_data&lt;&lt;&quot; &quot;;
                cur = cur-&gt;_LeftNode;
            }
            cout &lt;&lt; cur-&gt;_data&lt;&lt;&quot; &quot;;
            cur = cur-&gt;_RightNode;
        }
        cout &lt;&lt; endl;
    }
</code></pre><p><strong>&#x4E2D;&#x5E8F;&#x7EBF;&#x7D22;&#x5316;&#xFF1A;</strong></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201205200936.png" alt="image-20201205200935906"></p>
<pre><code>void _InOrder_Th(Node* root, Node*&amp; prev)
    {
        if (root == NULL)
        {
            return;
        }
        else
        {
            _InOrder_Th(root-&gt;_LeftNode, prev);
            if (root-&gt;_LeftNode == NULL)
            {
                root-&gt;_LeftNode = prev;
                root-&gt;LeftTag = THREAD;
            }
            if (prev&amp;&amp;prev-&gt;_RightNode == NULL)
            {
                prev-&gt;_RightNode = root;
                prev-&gt;RightTag = THREAD;
            }
            prev = root;
            _InOrder_Th(root-&gt;_RightNode, prev);
        }
    }
</code></pre><p>&#x4E2D;&#x5E8F;&#x7EBF;&#x7D22;&#x5316;&#x7684;&#x904D;&#x5386;&#xFF1A;</p>
<pre><code>void InOrder()
    {
        Node* cur = _root;

        while (cur)
        {
            //&#x627E;&#x5230;&#x6700;&#x5DE6;&#x7684;&#x70B9;
            while (cur-&gt;LeftTag == LINK)
            {
                cur = cur-&gt;_LeftNode;
            }
            cout &lt;&lt; cur-&gt;_data &lt;&lt; &quot; &quot;;
            while (cur-&gt;RightTag == THREAD)
            {
                cur = cur-&gt;_RightNode;
                cout &lt;&lt; cur-&gt;_data &lt;&lt; &quot; &quot;;
            }
            cur = cur-&gt;_RightNode;
        }   
        cout &lt;&lt; endl;
    }
</code></pre><h2 id="&#x4E03;-haffman&#x6811;"><a name="&#x4E03;-haffman&#x6811;" class="anchor-navigation-ex-anchor" href="#&#x4E03;-haffman&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="&#x4E03;-haffman&#x6811;" class="plugin-anchor" href="#&#x4E03;-haffman&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>&#x4E03; Haffman&#x6811;</h2>
<h3 id="1haffman&#x7F16;&#x7801;"><a name="1haffman&#x7F16;&#x7801;" class="anchor-navigation-ex-anchor" href="#1haffman&#x7F16;&#x7801;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1haffman&#x7F16;&#x7801;" class="plugin-anchor" href="#1haffman&#x7F16;&#x7801;"><i class="fa fa-link" aria-hidden="true"></i></a>1.Haffman&#x7F16;&#x7801;</h3>
<p>&#x54C8;&#x592B;&#x66FC;&#x7F16;&#x7801;&#xFF0C;&#x4E3B;&#x8981;&#x76EE;&#x7684;&#x662F;&#x6839;&#x636E;&#x4F7F;&#x7528;&#x9891;&#x7387;&#x6765;&#x6700;&#x5927;&#x5316;&#x8282;&#x7701;&#x5B57;&#x7B26;&#xFF08;&#x7F16;&#x7801;&#xFF09;&#x7684;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#x3002;</p>
<p>&#x7B80;&#x6613;&#x7684;&#x7406;&#x89E3;&#x5C31;&#x662F;&#xFF0C;&#x5047;&#x5982;&#x6211;&#x6709;A,B,C,D,E&#x4E94;&#x4E2A;&#x5B57;&#x7B26;&#xFF0C;&#x51FA;&#x73B0;&#x7684;&#x9891;&#x7387;&#xFF08;&#x5373;&#x6743;&#x503C;&#xFF09;&#x5206;&#x522B;&#x4E3A;5,4,3,2,1,&#x90A3;&#x4E48;&#x6211;&#x4EEC;&#x7B2C;&#x4E00;&#x6B65;&#x5148;&#x53D6;&#x4E24;&#x4E2A;&#x6700;&#x5C0F;&#x6743;&#x503C;&#x4F5C;&#x4E3A;&#x5DE6;&#x53F3;&#x5B50;&#x6811;&#x6784;&#x9020;&#x4E00;&#x4E2A;&#x65B0;&#x6811;&#xFF0C;&#x5373;&#x53D6;1&#xFF0C;2&#x6784;&#x6210;&#x65B0;&#x6811;&#xFF0C;&#x5176;&#x7ED3;&#x70B9;&#x4E3A;1+2=3&#xFF0C;&#x5982;&#x56FE;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201207153248.jpeg" alt="&#x8FD9;&#x91CC;&#x5199;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<p>&#x865A;&#x7EBF;&#x4E3A;&#x65B0;&#x751F;&#x6210;&#x7684;&#x7ED3;&#x70B9;&#xFF0C;&#x7B2C;&#x4E8C;&#x6B65;&#x518D;&#x628A;&#x65B0;&#x751F;&#x6210;&#x7684;&#x6743;&#x503C;&#x4E3A;3&#x7684;&#x7ED3;&#x70B9;&#x653E;&#x5230;&#x5269;&#x4E0B;&#x7684;&#x96C6;&#x5408;&#x4E2D;&#xFF0C;&#x6240;&#x4EE5;&#x96C6;&#x5408;&#x53D8;&#x6210;{5,4,3,3}&#xFF0C;&#x518D;&#x6839;&#x636E;&#x7B2C;&#x4E8C;&#x6B65;&#xFF0C;&#x53D6;&#x6700;&#x5C0F;&#x7684;&#x4E24;&#x4E2A;&#x6743;&#x503C;&#x6784;&#x6210;&#x65B0;&#x6811;&#xFF0C;&#x5982;&#x56FE;&#xFF1A;
<img src="https://gitee.com/zisuu/picture/raw/master/img/20201207153248.jpeg" alt="&#x8FD9;&#x91CC;&#x5199;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<p>&#x518D;&#x4F9D;&#x6B21;&#x5EFA;&#x7ACB;&#x54C8;&#x592B;&#x66FC;&#x6811;&#xFF0C;&#x5982;&#x4E0B;&#x56FE;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201207153248.jpeg" alt="&#x8FD9;&#x91CC;&#x5199;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<p>&#x5176;&#x4E2D;&#x5404;&#x4E2A;&#x6743;&#x503C;&#x66FF;&#x6362;&#x5BF9;&#x5E94;&#x7684;&#x5B57;&#x7B26;&#x5373;&#x4E3A;&#x4E0B;&#x56FE;&#xFF1A;</p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201207153248.jpeg" alt="&#x8FD9;&#x91CC;&#x5199;&#x56FE;&#x7247;&#x63CF;&#x8FF0;"></p>
<p>&#x6240;&#x4EE5;&#x5404;&#x5B57;&#x7B26;&#x5BF9;&#x5E94;&#x7684;&#x7F16;&#x7801;&#x4E3A;&#xFF1A;A-&gt;11,B-&gt;10,C-&gt;00,D-&gt;011,E-&gt;010
&#x970D;&#x592B;&#x66FC;&#x7F16;&#x7801;&#x662F;&#x4E00;&#x79CD;&#x65E0;&#x524D;&#x7F00;&#x7F16;&#x7801;&#x3002;&#x89E3;&#x7801;&#x65F6;&#x4E0D;&#x4F1A;&#x6DF7;&#x6DC6;&#x3002;&#x5176;&#x4E3B;&#x8981;&#x5E94;&#x7528;&#x5728;&#x6570;&#x636E;&#x538B;&#x7F29;&#xFF0C;&#x52A0;&#x5BC6;&#x89E3;&#x5BC6;&#x7B49;&#x573A;&#x5408;&#x3002;</p>
<p>&#x5982;&#x679C;&#x8003;&#x8651;&#x5230;&#x8FDB;&#x4E00;&#x6B65;&#x8282;&#x7701;&#x5B58;&#x50A8;&#x7A7A;&#x95F4;&#xFF0C;&#x5C31;&#x5E94;&#x8BE5;&#x5C06;&#x51FA;&#x73B0;&#x6982;&#x7387;&#x5927;&#xFF08;&#x5360;&#x6BD4;&#x591A;&#xFF09;&#x7684;&#x5B57;&#x7B26;&#x7528;&#x5C3D;&#x91CF;&#x5C11;&#x7684;0-1&#x8FDB;&#x884C;&#x7F16;&#x7801;&#xFF0C;&#x4E5F;&#x5C31;&#x662F;&#x66F4;&#x9760;&#x8FD1;&#x6839;&#xFF08;&#x8282;&#x70B9;&#x5C11;&#xFF09;&#xFF0C;&#x8FD9;&#x4E5F;&#x5C31;&#x662F;&#x6700;&#x4F18;&#x4E8C;&#x53C9;&#x6811;-&#x54C8;&#x592B;&#x66FC;&#x6811;&#x3002;</p>

<script>console.log("plugin-popup....");document.onclick = function(e){ e.target.tagName === "IMG" && window.open(e.target.src,e.target.src)}</script><style>img{cursor:pointer}</style>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="5.排序列题.html" class="navigation navigation-prev " aria-label="Previous page: 5.排序算法例题">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="7.树论例题.html" class="navigation navigation-next " aria-label="Next page: 7.树论例题.md">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"6.树论","level":"3.6","depth":1,"next":{"title":"7.树论例题.md","level":"3.7","depth":1,"path":"数据结构/7.树论例题.md","ref":"数据结构/7.树论例题.md","articles":[]},"previous":{"title":"5.排序算法例题","level":"3.5","depth":1,"path":"数据结构/5.排序列题.md","ref":"数据结构/5.排序列题.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-sharing","splitter","expandable-chapters-small","anchors","sharing-plus","anchor-navigation-ex","favicon","expandable-chapters","toggle-chapters","back-to-top-button","code","-lunr","-search","search-pro","pageview-count","popup","livereload"],"styles":{"website":"./styles/website.css"},"pluginsConfig":{"livereload":{},"splitter":{},"search-pro":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"popup":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"favicon":{},"back-to-top-button":{},"pageview-count":{},"expandable-chapters-small":{},"sharing":{"qq":false,"all":["google","facebook","weibo","twitter","qq","qzone","linkedin","pocket"],"douban":false,"facebook":false,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":false,"messenger":false,"line":false,"vk":false,"pocket":false,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"toggle-chapters":{},"expandable-chapters":{}},"theme":"default","author":"hzh","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"计算机 ,java , 大数据 基础知识体系","language":"zh-hans","gitbook":"3.2.3"},"file":{"path":"数据结构/6.树论.md","mtime":"2020-12-14T03:17:32.220Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-12-30T11:12:56.611Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-toggle-chapters/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-code/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-livereload/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

